Home | Issues | About JGAA | 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. 73-95, 2008. Regular paper.
Abstract The planarization method has proven to be successful in graph drawing.
The output, a combinatorial planar embedding of the so-called planarized
graph, can be combined with state-of-the-art 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 ec-planar, i.e., admits a planar
embedding satisfying the given embedding constraints. In the case that
G is ec-planar, we provide a linear time algorithm for computing the
corresponding ec-embedding. Otherwise, an ec-planar subgraph is
computed. The critical part is to re-insert 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 ec-planar graph H so that the insertion
is crossing minimal among all ec-planar embeddings of H. As a
side result, we characterize the set of all possible ec-planar
embeddings using BC- and SPQR-trees.
|
Journal Supporters
|