Planarity Testing and Optimal Edge Insertion with Embedding Constraints
Gutwenger, Carsten and Klein, Karsten and Mutzel, Petra (2007) Planarity Testing and Optimal Edge Insertion with Embedding Constraints. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 126-137 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_14).
Full text not available from this repository.
Many 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