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.

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

Repository Staff Only: item control page

References

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.