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 proceedingConference contributionAcademicpeer-review

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 languageEnglish
Title of host publicationGraph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings
EditorsDaniel Archambault, Csaba D. Tóth
Pages468-481
Number of pages14
DOIs
Publication statusPublished - 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11904 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

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.

Fingerprint Dive into the research topics of 'Homotopy Height, Grid-Major Height and Graph-Drawing Height'. Together they form a unique fingerprint.

Cite this