David Eppstein - The Widths of Strict Outerconfluent Graphs

dmtcs:12862 - Discrete Mathematics & Theoretical Computer Science, December 5, 2024, vol. 26:3 - https://doi.org/10.46298/dmtcs.12862
The Widths of Strict Outerconfluent GraphsArticle

Authors: David Eppstein

Strict outerconfluent drawing is a style of graph drawing in which vertices are drawn on the boundary of a disk, adjacencies are indicated by the existence of smooth curves through a system of tracks within the disk, and no two adjacent vertices are connected by more than one of these smooth tracks. We investigate graph width parameters on the graphs that have drawings in this style. We prove that the clique-width of these graphs is unbounded, but their twin-width is bounded.

Comment: Final version for DMTCS; 17 pages, 2 figures


Volume: vol. 26:3
Section: Graph Theory
Published on: December 5, 2024
Accepted on: November 13, 2024
Submitted on: January 12, 2024
Keywords: Mathematics - Combinatorics
Funding:
    Source : OpenAIRE Graph
  • Collaborative Research: AF: Medium: Algorithms for Geometric Graphs; Funder: National Science Foundation; Code: 2212129

Consultation statistics

This page has been seen 510 times.
This article's PDF has been downloaded 260 times.