Bibliographic Details
| Title: |
Constrained outer-string representations. |
| Authors: |
Biedl, Therese1 (AUTHOR) biedl@uwaterloo.ca, Cornelsen, Sabine2 (AUTHOR) sabine.cornelsen@uni-konstanz.de, Kratochvíl, Jan1,3 (AUTHOR) honza@kam.mff.cuni.cz, Rutter, Ignaz1,4 (AUTHOR) rutter@fim.uni-passau.de |
| Source: |
Discrete Applied Mathematics. Sep2026, Vol. 390, p114-134. 21p. |
| Subjects: |
Graph theory, Intersection graph theory, Algorithms |
| Abstract: |
An outer-string representation of a graph is an intersection representation in which each vertex is represented by a curve that is contained in the unit disk and has at least one endpoint on the boundary of the unit disk. In an outer-1-string representation the curves representing any two vertices are in addition allowed to intersect at most once. In this paper, we consider the following constrained version: Given a graph G plus a cyclic order v 1 , ... , v n of the vertices in G , test whether G has an outer-string or an outer-1-string representation in which the curves representing v 1 , ... , v n intersect the boundary of the unit disk in this order. We first show that a graph has an outer-string representation for all possible cyclic orders of the vertices if and only if the graph is the complement of a chordal graph. Then we turn towards the situation where one particular cyclic order of the vertices is fixed. We characterize the chordal graphs admitting a constrained outer-string representation and the trees and cycles admitting a constrained outer-1-string representation. The characterizations yield polynomial-time recognition and construction algorithms; in the case of outer-1-string representations the run time is linear. We also show how to decide in polynomial time whether an arbitrary graph admits a constrained L-shaped outer-1-string representation. In an L-shaped representation the curves are 1-bend orthogonal polylines anchored on a horizontal line, and they are contained in the half-plane below that line. However, not even all paths with a constrained outer-1-string representation admit one with L-shapes. We show that 2-bend orthogonal polylines are sufficient for trees and cycles with a constrained outer-1-string representation. [ABSTRACT FROM AUTHOR] |
|
Copyright of Discrete Applied Mathematics is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
