.png){kind=icon}
.png){kind=icon}
Return
Constrained outer-string representations
.png){kind=icon}
OA
AI
DOI：10.1016/j.dam.2026.04.018.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 v1, ... , vn of the vertices in G, test whether G has an outer-string or an outer-1-string representation in which the curves representing v1, ... , vn 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-1string 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. (c) 2026 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Keywords:
INTERSECTION GRAPHS
Journal
D
IF:
1.1
Papers:
336
Citations:
7.7K
Organization
View more organizations