Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. The Widths of Strict ...
Article

The Widths of Strict Outerconfluent Graphs

David Eppstein
Download article
Open on arXiv
Submitted on
January 12, 2024
Accepted on
November 13, 2024
Published on
December 5, 2024
Last modified on
March 27, 2025
Volume 26
vol. 26:3
Graph Theory
DOI
10.46298/dmtcs.12862
License
Attribution 4.0 International (CC BY 4.0)
National Science Foundation
2212129
Collaborative Research: AF: Medium: Algorithms for Geometric Graphs
Indicators
688
Views
395
Downloads

The Widths of Strict Outerconfluent Graphs

David Eppstein
Abstract
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
Keywords
  • Mathematics - Combinatorics
Mathematics Subject Classification 2020
  • 05C10 - Planar graphs; geometric and topological aspects of graph theory
  • 05C62 - Graph representations (geometric and intersection representations, etc.)
  • 05C85 - Graph algorithms (graph-theoretic aspects)
Preview
Loading PDF preview...