Recognition of Unit Segment and Polyline Graphs is ∃R-Complete

Michael Hoffmann; Tillmann Miltzow; Simon Weber; Lasse Wulf

doi:10.1007/978-3-031-75409-8_19

Recognition of Unit Segment and Polyline Graphs is ∃R-Complete

Michael Hoffmann, Tillmann Miltzow, Simon Weber^*, Lasse Wulf

^*Corresponding author for this work

Sub Algorithms and Complexity

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

Abstract

Given a set of objects O in the plane, the corresponding intersection graph is defined as follows. A vertex is created for each object and an edge joins two vertices whenever the corresponding objects intersect. We study here the case of unit segments and polylines with exactly k bends. In the recognition problem, we are given a graph and want to decide whether the graph can be represented as the intersection graph of certain geometric objects. In previous work it was shown that various recognition problems are ∃R-complete, leaving unit segments and polylines as few remaining natural cases. We show that recognition for both families of objects is ∃R-complete.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers
Editors	Daniel Kráľ, Martin Milanič
Publisher	Springer
Pages	266-281
Number of pages	16
ISBN (Electronic)	978-3-031-75409-8
ISBN (Print)	978-3-031-75408-1
DOIs	https://doi.org/10.1007/978-3-031-75409-8_19
Publication status	Published - 22 Jan 2025
Event	50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024 - Gozd Martuljek, Slovenia Duration: 19 Jun 2024 → 21 Jun 2024

Publication series

Name	Lecture Notes in Computer Science
Volume	14760
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024
Country/Territory	Slovenia
City	Gozd Martuljek
Period	19/06/24 → 21/06/24

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

Keywords

Intersection graphs
Polyline
Recognition
Unit segment

Access to Document

10.1007/978-3-031-75409-8_19

Cite this

Hoffmann, M., Miltzow, T., Weber, S., & Wulf, L. (2025). Recognition of Unit Segment and Polyline Graphs is ∃R-Complete. In D. Kráľ, & M. Milanič (Eds.), Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers (pp. 266-281). (Lecture Notes in Computer Science; Vol. 14760). Springer. https://doi.org/10.1007/978-3-031-75409-8_19

@inproceedings{c1500d8135d94463b2e0f1c08ceed55b,

title = "Recognition of Unit Segment and Polyline Graphs is ∃R-Complete",

abstract = "Given a set of objects O in the plane, the corresponding intersection graph is defined as follows. A vertex is created for each object and an edge joins two vertices whenever the corresponding objects intersect. We study here the case of unit segments and polylines with exactly k bends. In the recognition problem, we are given a graph and want to decide whether the graph can be represented as the intersection graph of certain geometric objects. In previous work it was shown that various recognition problems are ∃R-complete, leaving unit segments and polylines as few remaining natural cases. We show that recognition for both families of objects is ∃R-complete.",

keywords = "Intersection graphs, Polyline, Recognition, Unit segment",

author = "Michael Hoffmann and Tillmann Miltzow and Simon Weber and Lasse Wulf",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.; 50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024 ; Conference date: 19-06-2024 Through 21-06-2024",

year = "2025",

month = jan,

day = "22",

doi = "10.1007/978-3-031-75409-8\_19",

language = "English",

isbn = "978-3-031-75408-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "266--281",

editor = "Daniel Kr{\'a}{\v I} and Martin Milani{\v c}",

booktitle = "Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers",

}

Hoffmann, M, Miltzow, T, Weber, S & Wulf, L 2025, Recognition of Unit Segment and Polyline Graphs is ∃R-Complete. in D Kráľ & M Milanič (eds), Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers. Lecture Notes in Computer Science, vol. 14760, Springer, pp. 266-281, 50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024, Gozd Martuljek, Slovenia, 19/06/24. https://doi.org/10.1007/978-3-031-75409-8_19

Recognition of Unit Segment and Polyline Graphs is ∃R-Complete. / Hoffmann, Michael; Miltzow, Tillmann; Weber, Simon et al.
Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers. ed. / Daniel Kráľ; Martin Milanič. Springer, 2025. p. 266-281 (Lecture Notes in Computer Science; Vol. 14760).

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

TY - GEN

T1 - Recognition of Unit Segment and Polyline Graphs is ∃R-Complete

AU - Hoffmann, Michael

AU - Miltzow, Tillmann

AU - Weber, Simon

AU - Wulf, Lasse

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

PY - 2025/1/22

Y1 - 2025/1/22

N2 - Given a set of objects O in the plane, the corresponding intersection graph is defined as follows. A vertex is created for each object and an edge joins two vertices whenever the corresponding objects intersect. We study here the case of unit segments and polylines with exactly k bends. In the recognition problem, we are given a graph and want to decide whether the graph can be represented as the intersection graph of certain geometric objects. In previous work it was shown that various recognition problems are ∃R-complete, leaving unit segments and polylines as few remaining natural cases. We show that recognition for both families of objects is ∃R-complete.

AB - Given a set of objects O in the plane, the corresponding intersection graph is defined as follows. A vertex is created for each object and an edge joins two vertices whenever the corresponding objects intersect. We study here the case of unit segments and polylines with exactly k bends. In the recognition problem, we are given a graph and want to decide whether the graph can be represented as the intersection graph of certain geometric objects. In previous work it was shown that various recognition problems are ∃R-complete, leaving unit segments and polylines as few remaining natural cases. We show that recognition for both families of objects is ∃R-complete.

KW - Intersection graphs

KW - Polyline

KW - Recognition

KW - Unit segment

UR - http://www.scopus.com/inward/record.url?scp=85218465636&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-75409-8_19

DO - 10.1007/978-3-031-75409-8_19

M3 - Conference contribution

AN - SCOPUS:85218465636

SN - 978-3-031-75408-1

T3 - Lecture Notes in Computer Science

SP - 266

EP - 281

BT - Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers

A2 - Kráľ, Daniel

A2 - Milanič, Martin

PB - Springer

T2 - 50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024

Y2 - 19 June 2024 through 21 June 2024

ER -