BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Padmini Mukkamala appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We show that every cubic graph can be drawn in the plane with straight-line edges using only the four basic slopes $\{0,π/4,π/2,3π/4\}$. We also prove that four slopes have this property if and only if we can draw $K_4$ with them.
Given a graph $G$, an {\em obstacle representation} of $G$ is a set of points in the plane representing the vertices of $G$, together with a set of connected obstacles such that two vertices of $G$ are joined by an edge if and only if the corresponding points can be connected by a segment which avoids all obstacles. The {\em obstacle number} of $G$ is the minimum number of obstacles in an obstacle representation of $G$. It is shown that there are graphs on $n$ vertices with obstacle number at least $Ω({n}/{\log n})$.