## Planarity Testing and Optimal Edge Insertion with Embedding Constraints
Gutwenger, Carsten and Klein, Karsten and Mutzel, Petra
(2007)
Full text not available from this repository. ## AbstractMany practical applications demand additional restrictions on an admissible planar embedding. In particular, constraints on the permitted (clockwise) order of the edges around a vertex, like so-called side constraints, abound. In this paper, we introduce a set of hierarchical embedding constraints that also comprises side constraints. We present linear time algorithms for testing if a graph is ec-planar, i.e., admits a planar embedding satisfying the given embedding constraints, as well as for computing such an embedding. Moreover, we characterize the set of all possible ec-planar embeddings and consider the problem of finding a planar combinatorial embedding of a planar graph such that an additional edge can be inserted with the minimum number of crossings; we show that this problem can still be solved in linear time under the additional restrictions of embedding constraints.
Repository Staff Only: item control page References |