Result: Graphs with large total angular resolution

Title:
Graphs with large total angular resolution
Authors:
Aichholzer, Oswin, Korman Cozzetti, Matías, Okamoto, Yoshio, Parada Muñoz, Irene María de, Perz, Daniel, van Renssen, Andre, Vogtenhuber, Birgit
Contributors:
Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. DCCG - Discrete, Combinational, and Computational Geometry
Publication Year:
2023
Collection:
Universitat Politècnica de Catalunya, BarcelonaTech: UPCommons - Global access to UPC knowledge
Subject Terms:
Àrees temàtiques de la UPC::Matemàtiques i estadística, Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs, Computer science--Mathematics, Graph theory, Graph drawing, Total angular resolution, Angular resolution, Crossing resolution, NP-hardness, Informàtica--Matemàtica, Grafs, Teoria de, Classificació AMS::68 Computer science::68R Discrete mathematics in relation to computer science, Classificació AMS::05 Combinatorics::05C Graph theory
Document Type:
Academic journal article in journal/newspaper
File Description:
16 p.; application/pdf
Language:
English
Relation:
https://www.sciencedirect.com/science/article/pii/S0304397522007320; http://hdl.handle.net/2117/404001
DOI:
10.1016/j.tcs.2022.12.010
Availability:
http://hdl.handle.net/2117/404001
https://doi.org/10.1016/j.tcs.2022.12.010
Rights:
Attribution-NonCommercial-NoDerivatives 4.0 International ; http://creativecommons.org/licenses/by-nc-nd/4.0/ ; Open Access
Accession Number:
edsbas.31B66637
Database:
BASE

Further Information

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 is NP-hard. Further we present some special graphs and their total angular resolution. ; Peer Reviewed ; Postprint (published version)