Circular separation dimension of a subclass of planar graphs

zbMATH Open1401.05078arXiv1612.09436MaRDI QIDQ4560209FDOQ4560209

Authors: Arpitha P. Bharathi, Minati De, Abhiruk Lahiri 

Publication date: 10 December 2018

Abstract: A pair of non-adjacent edges is said to be separated in a circular ordering of vertices, if the endpoints of the two edges do not alternate in the ordering. The circular separation dimension of a graph $G$, denoted by $p{i}^{c}irc(G)$, is the minimum number of circular orderings of the vertices of $G$ such that every pair of non-adjacent edges is separated in at least one of the circular orderings. This notion is introduced by Loeb and West in their recent paper. In this article, we consider two subclasses of planar graphs, namely $2$-outerplanar graphs and series-parallel graphs. A $2$-outerplanar graph has a planar embedding such that the subgraph obtained by removal of the vertices of the exterior face is outerplanar. We prove that if $G$ is $2$-outerplanar then $p{i}^{c}irc(G)=2$. We also prove that if $G$ is a series-parallel graph then $p{i}^{c}irc(G)leq2$.

Full work available at URL: https://arxiv.org/abs/1612.09436

Recommendations

• Fractional and circular separation dimension of graphs
• Separation dimension of bounded degree graphs
• Circularity of planar graphs
• Separation dimension and degree
• On the order dimension of outerplanar maps

zbMATH Keywords

planar graphseries-parallel graph2-outerplanar graphcircular separation dimension

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Cited In (3)

• Separation dimension and degree
• Fractional and circular separation dimension of graphs
• Perfect and nearly perfect separation dimension of complete and random graphs

This page was built for publication: Circular separation dimension of a subclass of planar graphs

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