Information Technology Reference
In-Depth Information
On the Recognition of Fan-Planar
and Maximal Outer-Fan-Planar Graphs
Michael A. Bekos 1 , Sabine Cornelsen 2 ,Luca Grilli 3 ,
Seok-Hee Hong 4 , and Michael Kaufmann 1
1
Wilhelm-Schickard-Institutfur Informatik, Universitat T ubingen, Germany
{ bekos,mk } @informatik.uni-tuebingen.de
2
Dept. of Computer and Information Science, University of Konstanz, Germany
sabine.cornelsen@uni-konstanz.de
3
Dipartimento di Ingegneria, Universit`adegli Studi di Perugia, Italy
luca.grilli@unipg.it
4
School of Information Technologies, University of Sydney, Australia
shhong@it.usyd.edu.au
Abstract. Fan-planar graphs were recently introduced as a generalization of
1- planar graphs. A graph is fan-planar if it can be embedded in the plane, such
that each edge that is crossed more than once, is crossed by a bundle of two or
more edges incident to a common vertex. A graph is outer-fan-planar if it has
a fan-planar embedding in which every vertex is on the outer face. If, in addi-
tion, the insertion of an edge destroys its outer-fan-planarity, then it is maximal
outer-fan-planar .
In this paper, we present a polynomial-time algorithm to test whether a given
graph is maximalouter-fan-planar .Thealgorithm can also be employed to pro-
duce an outer-fan-planar embedding, if one exists. On the negative side, we show
that testing fan-planarity of a graph is NP-hard, for the case where the rotation
system (i.e., the cyclic order of the edges around each vertex) is given.
1
Introduction
A simple drawing of a graph is a representation of a graph in the plane, where each
vertex is represented by a point and each edgeisaJordancurve connecting its endpoints
such that no edge contains a vertex in its interior, no two edges incident to a common
end-vertex cross, no edge crosses itself, no two edges meet tangentially, and no two
edges cross more than once.
An important subclass of drawn graphs is the class of planar graphs, in which there
exist no crossings between edges. Although planarity is one of the most desirable prop-
erties when drawing a graph, many real-world graphs are in fact non-planar.
This work started at the Bertinoro Workshop onGraphDrawing 2014 . The work of Bekos is
implemented within the framework of the Action “SupportingPostdoctoral Researchers” of
the Operational Program “Education and Lifelong Learning” (Action's Beneficiary: General
Secretariat for Research and Technology), and is co-financed by the European Social Fund
(ESF) and the Greek State. Grilli was partly supported by the MIUR project AMANDA “Al-
gorithmics for MAssive and Networked DAta”, prot. 2012C4E3KT 001. Hong was supported
by ARC Future Fellowship and Humboldt Fellowship.
Search WWH ::




Custom Search