Constrained outer-string representations.
Saved in:
| 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 |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 193680376 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Constrained outer-string representations. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Biedl%2C+Therese%22">Biedl, Therese</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> biedl@uwaterloo.ca</i><br /><searchLink fieldCode="AR" term="%22Cornelsen%2C+Sabine%22">Cornelsen, Sabine</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> sabine.cornelsen@uni-konstanz.de</i><br /><searchLink fieldCode="AR" term="%22Kratochvíl%2C+Jan%22">Kratochvíl, Jan</searchLink><relatesTo>1,3</relatesTo> (AUTHOR)<i> honza@kam.mff.cuni.cz</i><br /><searchLink fieldCode="AR" term="%22Rutter%2C+Ignaz%22">Rutter, Ignaz</searchLink><relatesTo>1,4</relatesTo> (AUTHOR)<i> rutter@fim.uni-passau.de</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Discrete+Applied+Mathematics%22">Discrete Applied Mathematics</searchLink>. Sep2026, Vol. 390, p114-134. 21p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Graph+theory%22">Graph theory</searchLink><br /><searchLink fieldCode="DE" term="%22Intersection+graph+theory%22">Intersection graph theory</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=193680376 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1016/j.dam.2026.04.018 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 21 StartPage: 114 Subjects: – SubjectFull: Graph theory Type: general – SubjectFull: Intersection graph theory Type: general – SubjectFull: Algorithms Type: general Titles: – TitleFull: Constrained outer-string representations. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Biedl, Therese – PersonEntity: Name: NameFull: Cornelsen, Sabine – PersonEntity: Name: NameFull: Kratochvíl, Jan – PersonEntity: Name: NameFull: Rutter, Ignaz IsPartOfRelationships: – BibEntity: Dates: – D: 15 M: 09 Text: Sep2026 Type: published Y: 2026 Identifiers: – Type: issn-print Value: 0166218X Numbering: – Type: volume Value: 390 Titles: – TitleFull: Discrete Applied Mathematics Type: main |
| ResultId | 1 |
