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 , pp. 126-137(Official URL:

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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-70904-6_14
Classifications: P Styles > P.540 Planar
M Methods > M.700 Planarization-based
G Algorithms and Complexity > G.770 Planarity Testing

Actions (login required)

View Item View Item