Homotopy Height, Grid-Major Height and Graph-Drawing Height
| Autor: | David Eppstein, Arnaud de Mesmay, Therese C. Biedl, Tim Ophelders, Erin Wolf Chambers |
|---|---|
| Přispěvatelé: | David R. Cheriton School of Computer Science, University of Waterloo [Waterloo], Saint Louis University, Department of computer science [Irvine], University of California [Irvine] (UCI), University of California-University of California, Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, Michigan State University System |
| Rok vydání: | 2019 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences Discrete mathematics 050101 languages & linguistics Homotopy [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] 05 social sciences 02 engineering and technology Computer Science::Computational Geometry [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] Grid Graph Pathwidth Planar Graph drawing Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Computer Science - Computational Geometry Data Structures and Algorithms (cs.DS) 020201 artificial intelligence & image processing 0501 psychology and cognitive sciences ComputingMilieux_MISCELLANEOUS Mathematics |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030358013 Graph Drawing Graph Drawing 2019 Graph Drawing 2019, Sep 2019, Prague, Czech Republic |
| Popis: | It is well-known that both the pathwidth and the outer-planarity of a graph can be used to obtain lower bounds on the height of a planar straight-line drawing of a graph. But both bounds fall short for some graphs. In this paper, we consider two other parameters, the (simple) homotopy height and the (simple) grid-major height. We discuss the relationship between them and to the other parameters, and argue that they give lower bounds on the straight-line drawing height that are never worse than the ones obtained from pathwidth and outer-planarity. Comment: 28 pages, 11 figures. Expanded version of a paper in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019); for the proceedings version, see version 1 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|