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

Bibliographical note

DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

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",

note = "DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",

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

N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

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 - http://www.scopus.com/inward/record.url?scp=85076890118&partnerID=8YFLogxK

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

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this