Manhattan-Geodesic Embedding of Planar Graphs

Katz, Bastian and Krug, Marcus and Rutter, Ignaz and Wolff, Alexander (2010) Manhattan-Geodesic Embedding of Planar Graphs. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009, Chicago, IL, USA , pp. 207-218 (Official URL:

Full text not available from this repository.


In this paper, we explore a new convention for drawing graphs, the (Manhattan-) geodesic drawing convention. It requires that edges are drawn as interior-disjoint monotone chains of axis-parallel line segments, that is, as geodesics with respect to the Manhattan metric. First, we show that geodesic embeddability on the grid is equivalent to 1-bend embeddability on the grid. For the latter question an efficient algorithm has been proposed. Second, we consider geodesic point-set embeddability where the task is to decide whether a given graph can be embedded on a given point set. We show that this problem is N P-hard. In contrast, we efficiently solve geodesic polygonization—the special case where the graph is a cycle. Third, we consider geodesic point-set embeddability where the vertex–point correspondence is given. We show that on the grid, this problem is N P-hard even for perfect matchings, but without the grid restriction, we solve the matching problem efficiently.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-11805-0_21
Classifications:P Styles > P.600 Poly-line > P.600.700 Orthogonal
G Algorithms and Complexity > G.490 Embeddings
ID Code:1092

Repository Staff Only: item control page


Cabello, S.: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. J. Graph Algorithms Appl. 10(2), 353–363 (2006)

Demaine, E.: Simple polygonizations (2007), (Accessed May 30, 2009)

Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)

Goaoc, X., Kratochvíl J., Okamoto, Y., Shin, C.-S., Spillner, A., Wolff, A.: Untangling a planar graph. Discrete Comput. Geom (2009),

Hurtado, F.: Personal communication (2006)

Katz, B., Krug, M., Rutter, I., Wolff, A.: Manhattan-geodesic point-set embeddability and polygonization. Technical Report 2009-17, Universität Karlsruhe(2009),

Kaufmann, M., Wiese, R.: Embedding vertices at points: Few bends suffice for planar graphs. J. Graph Algorithms Appl. 6(1), 115–129 (2002)

Liu, Y., Marchioro, P., Petreschi, R., Simeone, B.: Theoretical results on at most 1-bend embeddability of graphs. Acta Math. Appl. Sinica (English Ser.) 8(2), 188– 192 (1992)

O’Rourke, J.: Uniqueness of orthogonal connect-the-dots. In: Toussaint, G. (ed.) Computational Morphology, pp. 97–104. North-Holland, Amsterdam (1988)

Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. Graph. Combinator. 17(4), 717–728 (2001)

Raghavan, R., Cohoon, J., Sahni, S.: Single bend wiring. J. Algorithms 7(2), 232– 257 (1986)

Rappaport, D.: On the complexity of computing orthogonal polygons from a set of points. Technical Report SOCS-86.9, McGill University, Montréal (1986)

Rendl, F., Woeginger, G.: Reconstructing sets of orthogonal line segments in the plane. Discrete Math 119(1-3), 167–174 (1993)

Schnyder, W.: Embedding planar graphs on the grid. In: Proc. 1st ACM-SIAM Symp. on Discrete Algorithms (SODA 1990), pp. 138–148 (1990)

Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16(3), 421–444 (1987)