The arc-width of a graph

Publication date 11 December 2001

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/122094, http://www.emis.de/journals/EJC/Volume_8/Abstracts/v8i1r34.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

arc-represention

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph minors (05C83)

Review text

An arc-represention of a graph \(G\) maps the vertices of \(G\) to arcs of a circle such that adjacent vertices are mapped to intersecting arcs. The arc-width of a representation is the maximum number of arcs containing a given point \(P\). The arc-width of a graph \(G\), \(\text{aw}(G)\), is the minimal arc-width over all of its arc-representations. NEWLINENEWLINENEWLINEThis parameter is closely related to interval representations of a graph, where the corresponding parameter is called the interval-width of a graph. It is also related to the more common path-width of a graph, and the vortex-width of a graph. In this paper, the authors relate these parameters, including a proof that \(\text{aw}(K_{s,s}) = s\). They also ask a number of interesting questions about these parameters.

Recommendations

Cited in

(3)

This page was built for publication: The arc-width of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5949342)