Computer Science – Discrete Mathematics
Scientific paper
2008-03-06
Discrete Applied Mathematics 159:8 (2011) 789-799
Computer Science
Discrete Mathematics
18 pages, 4 figures. Lemma 3.3 is corrected, several amendments are made throughout the paper
Scientific paper
10.1016/j.dam.2011.01.011
Given a planar graph $G$, we consider drawings of $G$ in the plane where edges are represented by straight line segments (which possibly intersect). Such a drawing is specified by an injective embedding $\pi$ of the vertex set of $G$ into the plane. We prove that a wheel graph $W_n$ admits a drawing $\pi$ such that, if one wants to eliminate edge crossings by shifting vertices to new positions in the plane, then at most $(2+o(1))\sqrt n$ of all $n$ vertices can stay fixed. Moreover, such a drawing $\pi$ exists even if it is presupposed that the vertices occupy any prescribed set of points in the plane. Similar questions are discussed for other families of planar graphs.
Kang Mihyun
Pikhurko Oleg
Ravsky Alexander
Schacht Mathias
Verbitsky Oleg
No associations
LandOfFree
Untangling planar graphs from a specified vertex position - Hard cases does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Untangling planar graphs from a specified vertex position - Hard cases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Untangling planar graphs from a specified vertex position - Hard cases will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-13784