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:

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
ID Code:768

Repository Staff Only: item control page


C. Batini, M. Talamo, and R. Tamassia. Computer aided layout of entity relationship diagrams. Journal of Systems and Software, 4:163-173, 1984.

K.-F. Böhringer and F. N. Paulisch. Using constraints to achieve stability in automatic graph layout algorithms. In Proc. of CHI-90, pages 43-51, 1990.

U. Brandes, M. Eiglsperger, M. Kaufmann, and D. Wagner. Sketch-driven orthogonal graph drawing. In Proc. GD 2002, volume 2528 of LNCS, pages 1-11, 2002.

Ulrik Brandes and Dorothea Wagner. A bayesian paradigm for dynamic graph layout. In Proc. GD '97, volume 1353 of LNCS, pages 236-247, 1997.

N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa. A linear algorithm for embedding planar graphs using PQ-trees. J. Computer and System Sciences, 30:54-76, 1985.

G. Di Battista, W. Didimo, M. Patrignani, and M. Pizzonia. Drawing database schemas. Softw. Pract. Exper., 32(11):1065-1098, 2002.

G. Di Battista and R. Tamassia. On-line planarity testing. SIAM J. Comput., 25(5):956-997, 1996.

C. Dornheim. Planar graphs with topological constraints. J. Graph Algorithms Appl, 6(1):27-66, 2002.

M. R. Garey and D. S. Johnson. Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods, 4(3):312-316, 1983.

C. Gutwenger, K. Klein, and P. Mutzel. Planarity testing and optimal edge insertion with embedding constraints. Technical Report TR06-1-005, Chair of Algorithm Engineering, University of Dortmund, 2006.

C. Gutwenger and P. Mutzel. A linear time implementation of SPQR trees. In J. Marks, editor, Proc. GD 2000, volume 1984 of LNCS, pages 77-90, 2001.

C. Gutwenger and P. Mutzel. An experimental study of crossing minimization heuristics. In G. Liotta, editor, Proc. GD 2003, volume 2912 of LNCS, pages 13-24, 2004.

C. Gutwenger, P. Mutzel, and R. Weiskircher. Inserting an edge into a planar graph. Algorithmica, 41(4):289-308, 2005.

J. Hopcroft and R. E. Tarjan. Efficient planarity testing. Journal of the ACM, 21(4):549-568, 1974.

Stephen C. North. Incremental layout in DynaDAG. In Proc. GD '95, volume 1027 of LNCS, pages 409-418, 1996.