Graphs with large total angular resolution

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

doi:10.1016/j.tcs.2022.12.010

Graphs with large total angular resolution

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

^*Corresponding author for this work

Institute of Software Engineering and Artificial Intelligence (7160)

Research output: Contribution to journal › Article › 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 tight bounds for the number of edges for graphs for some values of the total angular resolution up to a finite number of well specified exceptions of constant size. In addition, we show that deciding whether a graph has total angular resolution at least 60^∘ is NP-hard. Further we present some special graphs and their total angular resolution.

Original language	English
Pages (from-to)	73-88
Number of pages	16
Journal	Theoretical Computer Science
Volume	943
DOIs	https://doi.org/10.1016/j.tcs.2022.12.010
Publication status	Published - 17 Jan 2023

Keywords

Angular resolution
Crossing resolution
Graph drawing
NP-hardness
Total angular resolution

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Fields of Expertise

Information, Communication & Computing

Access to Document

10.1016/j.tcs.2022.12.010Licence: CC BY 4.0

Cite this

@article{bbfaf4527bbc48a39e3ae916c878d826,

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 tight bounds for the number of edges for graphs for some values of the total angular resolution up to a finite number of well specified exceptions of constant size. In addition, we show that deciding whether a graph has total angular resolution at least 60∘ is NP-hard. Further we present some special graphs and their total angular resolution.",

keywords = "Angular resolution, Crossing resolution, Graph drawing, NP-hardness, Total angular resolution",

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

note = "Publisher Copyright: {\textcopyright} 2022 The Authors",

year = "2023",

month = jan,

day = "17",

doi = "10.1016/j.tcs.2022.12.010",

language = "English",

volume = "943",

pages = "73--88",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Graphs with large total angular resolution

AU - Aichholzer, Oswin

AU - Korman, Matias

AU - Okamoto, Yoshio

AU - Parada, Irene

AU - Perz, Daniel

AU - van Renssen, André

AU - Vogtenhuber, Birgit

PY - 2023/1/17

Y1 - 2023/1/17

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 tight bounds for the number of edges for graphs for some values of the total angular resolution up to a finite number of well specified exceptions of constant size. In addition, we show that deciding whether a graph has total angular resolution at least 60∘ is NP-hard. Further we present some special graphs and their total angular resolution.

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 tight bounds for the number of edges for graphs for some values of the total angular resolution up to a finite number of well specified exceptions of constant size. In addition, we show that deciding whether a graph has total angular resolution at least 60∘ is NP-hard. Further we present some special graphs and their total angular resolution.

KW - Angular resolution

KW - Crossing resolution

KW - Graph drawing

KW - NP-hardness

KW - Total angular resolution

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

U2 - 10.1016/j.tcs.2022.12.010

DO - 10.1016/j.tcs.2022.12.010

M3 - Article

AN - SCOPUS:85145238411

SN - 0304-3975

VL - 943

SP - 73

EP - 88

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Graphs with large total angular resolution

Abstract

Keywords

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Other files and links

Cite this