Constrained Outer-String Representations

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10493338" target="_blank" >RIV/00216208:11320/24:10493338 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.4230/LIPIcs.GD.2024.10" target="_blank" >https://doi.org/10.4230/LIPIcs.GD.2024.10</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.GD.2024.10" target="_blank" >10.4230/LIPIcs.GD.2024.10</a>

Result language

angličtina

Original language name

Constrained Outer-String Representations

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GX23-04949X" target="_blank" >GX23-04949X: Fundamental questions of discrete geometry</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2024

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

32nd International Symposium on Graph Drawing and Network Visualization, GD 2024, September 18-20, 2024, Vienna, Austria

ISBN

978-3-95977-343-0

ISSN

—

e-ISSN

—

Number of pages

18

Pages from-to

1-18

Publisher name

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Place of publication

Dagstuhl

Event location

Wien

Event date

Sep 18, 2024

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—