Rook-drawings of Plane Graphs
| Autor: | David Auber, Paul Dorbec, Claire Pennarun, Nicolas Bonichon |
|---|---|
| Přispěvatelé: | Pennarun, Claire, Jeunes Chercheuses et Jeunes Chercheurs - Graphes Plongés et leurs Structures Orientées - - EGOS2012 - ANR-12-JS02-0002 - JC - VALID, 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), Projet 'Request' (PIAO18062-645401) - Programme 'Investissement d'Avenir' (Big Data - Cloud Computing), ANR-12-JS02-0002,EGOS,Graphes Plongés et leurs Structures Orientées(2012) |
| Předmět: |
General Computer Science
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] 02 engineering and technology Computer Science::Computational Geometry Theoretical Computer Science Combinatorics Indifference graph symbols.namesake Pathwidth Chordal graph Outerplanar graph 0202 electrical engineering electronic engineering information engineering Mathematics::Representation Theory Mathematics Discrete mathematics Mathematics::Combinatorics Book embedding 020207 software engineering 1-planar graph Computer Science Applications Planar graph Computational Theory and Mathematics symbols 020201 artificial intelligence & image processing Geometry and Topology MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | HAL Journal of Graph Algorithms and Applications Journal of Graph Algorithms and Applications, Brown University, 2017, 21 (1), pp.103-120 |
| ISSN: | 1526-1719 |
| Popis: | International audience; We introduce a new type of graph drawing called " rook-drawing ". A 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: |
|