ManhattanGeodesic Embedding of Planar GraphsKatz, Bastian and Krug, Marcus and Rutter, Ignaz and Wolff, Alexander (2010) ManhattanGeodesic Embedding of Planar Graphs. In: Graph Drawing 17th International Symposium, GD 2009, September 2225, 2009 , pp. 207218(Official URL: http://dx.doi.org/10.1007/9783642118050_21). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642118050_21
AbstractIn this paper, we explore a new convention for drawing graphs, the (Manhattan) geodesic drawing convention. It requires that edges are drawn as interiordisjoint monotone chains of axisparallel line segments, that is, as geodesics with respect to the Manhattan metric. First, we show that geodesic embeddability on the grid is equivalent to 1bend embeddability on the grid. For the latter question an eﬃcient algorithm has been proposed. Second, we consider geodesic pointset 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 Phard. In contrast, we eﬃciently solve geodesic polygonization—the special case where the graph is a cycle. Third, we consider geodesic pointset embeddability where the vertex–point correspondence is given. We show that on the grid, this problem is N Phard even for perfect matchings, but without the grid restriction, we solve the matching problem eﬃciently.
Actions (login required)
