Name
Abstract | ||
|---|---|---|
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 $\mathcal{NP}$-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 $\mathcal{NP}$-hard even for perfect matchings, but without the grid restriction, we solve the matching problem efficiently. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-11805-0_21 | Graph Drawing |
Keywords | Field | DocType |
point correspondence,new convention,grid restriction,planar graph,point set,geodesic embeddability,geodesic point-set embeddability,manhattan-geodesic embedding,matching problem,1-bend embeddability,geodesic polygonization,geodesic drawing convention | Line segment,Discrete mathematics,Combinatorics,Embedding,Vertex (geometry),Hamiltonian path,Planar graph,Geodesic,Monotone polygon,Grid,Mathematics | Conference |
Volume | ISSN | ISBN |
5849 | 0302-9743 | 3-642-11804-6 |
Citations | PageRank | References |
17 | 1.00 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bastian Katz | 1 | 67 | 6.32 |
| Marcus Krug | 2 | 76 | 8.18 |
| Ignaz Rutter | 3 | 315 | 44.45 |
| Alexander Wolff | 4 | 222 | 22.66 |