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: http://dx.doi.org/10.1007/978-3-540-70904-6_14).

Full text not available from this repository.

Abstract

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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/768

Actions (login required)

View Item View Item