Abstract
dc:description.abstractA separating set of a connected graph $G$ is a set of vertices $S$ such that $G-S$ is disconnected. $S$ is a minimum separating set of $G$ if there is no separating set of $G$ with fewer vertices than $S$. The size of a minimum separating set of $G$ is called the vertex connectivity of $G$. A separating set of $G$ that is a cycle is called a separating cycle of $G$. Let $G$ be a planar graph with a given planar embedding. Let $\Lambda(G)$ be a supergraph of $G$ obtained by inserting a face vertex in each face of $G$ and connecting the face vertex to all vertices on the boundary of the face. It is well known that a set $S$ is a minimum separating set of a planar graph $G$ if and only if the vertices of $S$ can be connected together using face vertices to get a cycle $X$ of length $2|S|$ that is separating in $\Lambda(G)$. We extend this correspondence between separating sets and separating cycles from planar graphs to the class of bowtie 1-plane graphs. These are graphs that are embedded on the plane such that each edge is crossed at most once by another edge, and the endpoints of each such crossing induce either K4, K4 \setminus \{e\} or C4. Using this result, we give an algorithm to compute the vertex connectivity of a bowtie 1-plane graph in linear time.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2022
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Murali, Karthik
- Advisor dc:contributor.advisor
-
- Biedl, Therese
Subjects
dc:subject × 3Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/18446