Rook-drawing for plane graphs
| Autor: | Claire Pennarun, David Auber, Paul Dorbec, Nicolas Bonichon |
|---|---|
| Přispěvatelé: | Pennarun, Claire, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) |
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
Discrete mathematics
Book embedding Mathematics::Combinatorics Planar straight-line graph [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] Computer Science::Computational Geometry 1-planar graph Planar graph Combinatorics symbols.namesake Indifference graph Pathwidth Chordal graph Outerplanar graph symbols Mathematics::Representation Theory Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | HAL 23rd International Symposium on Graph Drawing and Network Visualization 23rd International Symposium on Graph Drawing and Network Visualization, Sep 2015, Los Angeles, United States Lecture Notes in Computer Science ISBN: 9783319272603 Graph Drawing |
| Popis: | International audience; Motivated by visualization of large graphs, we introduce a new type of graph drawing called ``rook-drawing".A \emph{rook-drawing} of a graph $G$ is obtained by placing the $n$ nodes of $G$ on the intersections of a regular grid, such that each row and column of the grid supports exactly one node. This paper focuses on rook-drawings of planar graphs.We first give a linear algorithm to compute a planar straight-line rook-drawing for outerplanar graphs.We then characterize the maximal planar graphs admitting a planar straight-line rook-drawing, which are unique for a given order.Finally, we give a linear time algorithm to compute a polyline planar rook-drawing for plane graphs with at most $n-3$ bent edges. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|