Home  Issues  Aims and Scope  Instructions for Authors 
Special Issue on Selected Papers from the Fourteenth International Symposium on Graph Drawing, GD 2006
DOI: 10.7155/jgaa.00160
Planarity Testing and Optimal Edge Insertion with Embedding Constraints
Vol. 12, no. 1, pp. 7395, 2008. Regular paper.
Abstract The planarization method has proven to be successful in graph drawing.
The output, a combinatorial planar embedding of the socalled planarized
graph, can be combined with stateoftheart planar drawing algorithms.
However, many practical applications have additional constraints on
the drawings that result in restrictions on the set of admissible planar
embeddings.
In this paper, we consider embedding constraints that restrict the
admissible order of incident edges around a vertex. Such constraints
occur in applications, e.g., from side or port constraints.
We introduce a set of hierarchical embedding constraints that
include grouping, oriented, and mirror constraints,
and show how these constraints can be integrated into the planarization
method. For this, we first present a linear time algorithm for testing
if a given graph G is ecplanar, i.e., admits a planar
embedding satisfying the given embedding constraints. In the case that
G is ecplanar, we provide a linear time algorithm for computing the
corresponding ecembedding. Otherwise, an ecplanar subgraph is
computed. The critical part is to reinsert the deleted edges subject to
the embedding constraints so that the number of crossings is kept
small. For this, we present a linear time algorithm which is able to
insert an edge into an ecplanar graph H so that the insertion
is crossing minimal among all ecplanar embeddings of H. As a
side result, we characterize the set of all possible ecplanar
embeddings using BC and SPQRtrees.
