Graphs with large total angular resolution

Oswin Aichholzer; Matias Korman; Yoshio Okamoto; Irene Maria De Parada; Daniel Perz; André van Renssen; Birgit Vogtenhuber

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

Graphs with large total angular resolution

Oswin Aichholzer
, Matias Korman
, Yoshio Okamoto
, Irene Maria De Parada
, Daniel Perz
, André van Renssen
, Birgit Vogtenhuber

Institute of Software Engineering and Artificial Intelligence (7160)

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

Abstract

The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawing: the angular resolution, which is the minimum angle between incident edges, and the crossing resolution, which is the minimum angle between crossing edges. We consider the total angular resolution of a graph, which is the maximum total angular resolution of a straight-line drawing of this graph. We prove that, up to a finite number of well specified exceptions of constant size, the number of edges of a graph with n vertices and a total angular resolution greater than 60° is bounded by 2n−6. This bound is tight. In addition, we show that deciding whether a graph has total angular resolution at least 60° is NP-hard.

Original language	English
Title of host publication	Graph Drawing and Network Visualization
Publisher	Springer, Cham
Chapter	Quality Metrics
Pages	193-199
Number of pages	7
ISBN (Electronic)	978-3-030-35802-0
ISBN (Print)	978-3-030-35801-3
DOIs	https://doi.org/10.1007/978-3-030-35802-0
Publication status	Published - 2019
Event	27th International Symposium on Graph Drawing and Network Visualization: GD 2019 - Hotel Floret, Pruhonice, Czech Republic Duration: 17 Sept 2019 → 20 Sept 2019 https://kam.mff.cuni.cz/gd2019/index.html https://kam.mff.cuni.cz/gd2019/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer, Cham
Number	11904
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	27th International Symposium on Graph Drawing and Network Visualization
Abbreviated title	GD 2019
Country/Territory	Czech Republic
City	Pruhonice
Period	17/09/19 → 20/09/19
Internet address	https://kam.mff.cuni.cz/gd2019/index.html https://kam.mff.cuni.cz/gd2019/

Fields of Expertise

Information, Communication & Computing

Access to Document

10.1007/978-3-030-35802-0

Cite this

Aichholzer, O, Korman, M, Okamoto, Y, De Parada, IM, Perz, D, Renssen, AV & Vogtenhuber, B 2019, Graphs with large total angular resolution. in Graph Drawing and Network Visualization. Lecture Notes in Computer Science, no. 11904, Springer, Cham, pp. 193-199, 27th International Symposium on Graph Drawing and Network Visualization, Pruhonice, Czech Republic, 17/09/19. https://doi.org/10.1007/978-3-030-35802-0

@inproceedings{608c8a2fee4f42148a742001656743e6,

title = "Graphs with large total angular resolution",

abstract = "The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawing: the angular resolution, which is the minimum angle between incident edges, and the crossing resolution, which is the minimum angle between crossing edges. We consider the total angular resolution of a graph, which is the maximum total angular resolution of a straight-line drawing of this graph. We prove that, up to a finite number of well specified exceptions of constant size, the number of edges of a graph with n vertices and a total angular resolution greater than 60° is bounded by 2n−6. This bound is tight. In addition, we show that deciding whether a graph has total angular resolution at least 60° is NP-hard.",

author = "Oswin Aichholzer and Matias Korman and Yoshio Okamoto and \{De Parada\}, \{Irene Maria\} and Daniel Perz and Renssen, \{Andr{\'e} van\} and Birgit Vogtenhuber",

year = "2019",

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

language = "English",

isbn = "978-3-030-35801-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Cham",

number = "11904",

pages = "193--199",

booktitle = "Graph Drawing and Network Visualization",

note = "27th International Symposium on Graph Drawing and Network Visualization : GD 2019, GD 2019 ; Conference date: 17-09-2019 Through 20-09-2019",

url = "https://kam.mff.cuni.cz/gd2019/index.html, https://kam.mff.cuni.cz/gd2019/",

}

TY - GEN

T1 - Graphs with large total angular resolution

AU - Aichholzer, Oswin

AU - Korman, Matias

AU - Okamoto, Yoshio

AU - De Parada, Irene Maria

AU - Perz, Daniel

AU - Renssen, André van

AU - Vogtenhuber, Birgit

PY - 2019

Y1 - 2019

N2 - The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawing: the angular resolution, which is the minimum angle between incident edges, and the crossing resolution, which is the minimum angle between crossing edges. We consider the total angular resolution of a graph, which is the maximum total angular resolution of a straight-line drawing of this graph. We prove that, up to a finite number of well specified exceptions of constant size, the number of edges of a graph with n vertices and a total angular resolution greater than 60° is bounded by 2n−6. This bound is tight. In addition, we show that deciding whether a graph has total angular resolution at least 60° is NP-hard.

AB - The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawing: the angular resolution, which is the minimum angle between incident edges, and the crossing resolution, which is the minimum angle between crossing edges. We consider the total angular resolution of a graph, which is the maximum total angular resolution of a straight-line drawing of this graph. We prove that, up to a finite number of well specified exceptions of constant size, the number of edges of a graph with n vertices and a total angular resolution greater than 60° is bounded by 2n−6. This bound is tight. In addition, we show that deciding whether a graph has total angular resolution at least 60° is NP-hard.

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

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

M3 - Conference paper

SN - 978-3-030-35801-3

T3 - Lecture Notes in Computer Science

SP - 193

EP - 199

BT - Graph Drawing and Network Visualization

PB - Springer, Cham

T2 - 27th International Symposium on Graph Drawing and Network Visualization

Y2 - 17 September 2019 through 20 September 2019

ER -