Arpitha P. Bharathi ; Minati De ; Abhiruk Lahiri - Circular Separation Dimension of a Subclass of Planar Graphs

dmtcs:2661 - Discrete Mathematics & Theoretical Computer Science, November 3, 2017, Vol. 19 no. 3 - https://doi.org/10.23638/DMTCS-19-3-8
Circular Separation Dimension of a Subclass of Planar GraphsArticle

Authors: Arpitha P. Bharathi ; Minati De ORCID; Abhiruk Lahiri

    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 $\pi^\circ(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 $\pi^\circ(G) = 2$. We also prove that if $G$ is a series-parallel graph then $\pi^\circ(G) \leq 2$.


    Volume: Vol. 19 no. 3
    Section: Graph Theory
    Published on: November 3, 2017
    Accepted on: September 21, 2017
    Submitted on: January 20, 2017
    Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 839 times.
    This article's PDF has been downloaded 508 times.