Homotopy Height, Grid-Major Height and Graph-Drawing Height

Therese C. Biedl; Erin Wolf Chambers; David Eppstein; Arnaud de Mesmay; Tim Ophelders

doi:10.1007/978-3-030-35802-0_36

Homotopy Height, Grid-Major Height and Graph-Drawing Height

Therese C. Biedl
, Erin Wolf Chambers
, David Eppstein
, Arnaud de Mesmay
, Tim Ophelders

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

Abstract

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-minor 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.

Original language	English
Title of host publication	Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings
Editors	Daniel Archambault, Csaba D. Tóth
Pages	468-481
Number of pages	14
DOIs	https://doi.org/10.1007/978-3-030-35802-0_36
Publication status	Published - 2019

Publication series

Name	Lecture Notes in Computer Science

Access to Document

10.1007/978-3-030-35802-0_36

Cite this

Biedl, T. C., Chambers, E. W., Eppstein, D., Mesmay, A. D., & Ophelders, T. (2019). Homotopy Height, Grid-Major Height and Graph-Drawing Height. In D. Archambault, & C. D. Tóth (Eds.), Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings (pp. 468-481). (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-030-35802-0_36

@inproceedings{4c51d436c9d34f30bd55e0a499ea53db,

title = "Homotopy Height, Grid-Major Height and Graph-Drawing Height",

abstract = "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-minor 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.",

author = "Biedl, \{Therese C.\} and Chambers, \{Erin Wolf\} and David Eppstein and Mesmay, \{Arnaud de\} and Tim Ophelders",

year = "2019",

doi = "10.1007/978-3-030-35802-0\_36",

language = "English",

isbn = "9783030358013",

series = "Lecture Notes in Computer Science",

pages = "468--481",

editor = "Daniel Archambault and T{\'o}th, \{Csaba D.\}",

booktitle = "Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings",

}

Homotopy Height, Grid-Major Height and Graph-Drawing Height. / Biedl, Therese C.; Chambers, Erin Wolf; Eppstein, David et al.
Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings. ed. / Daniel Archambault; Csaba D. Tóth. 2019. p. 468-481 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Homotopy Height, Grid-Major Height and Graph-Drawing Height

AU - Biedl, Therese C.

AU - Chambers, Erin Wolf

AU - Eppstein, David

AU - Mesmay, Arnaud de

AU - Ophelders, Tim

PY - 2019

Y1 - 2019

N2 - 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-minor 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.

AB - 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-minor 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.

UR - https://www.scopus.com/pages/publications/85076890118

U2 - 10.1007/978-3-030-35802-0_36

DO - 10.1007/978-3-030-35802-0_36

M3 - Conference contribution

SN - 9783030358013

T3 - Lecture Notes in Computer Science

SP - 468

EP - 481

BT - Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings

A2 - Archambault, Daniel

A2 - Tóth, Csaba D.

ER -

Homotopy Height, Grid-Major Height and Graph-Drawing Height

Abstract

Publication series

Access to Document

Other files and links

Fingerprint

Cite this