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 , 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

Actions (login required)

View Item View Item