1
$\begingroup$

Consider a (simple) convex drawing of a $3$-connected planar graph $G$. (Edit:) Let us also assume that the border polygon has at least $4$ sides.

My question is as follows: does there exist a simple path in the graph connecting two boundary points in such a way that it separates the boundary polygon in two polygons of smaller perimeter (or at least not greater)?

Equivalently, do there always exist two points on the boundary such that (one of) the shortest path (in the induced plane metric) connecting them is not either of the boundary paths (and, ideally, does not intersect the boundary other than in the endpoints)?

The statement obviously does not hold for a non-convex drawing, but I was not able to produce an easy counterexample in the convex case. (I hope I didn't miss something obvious.)

Thank you.

Edit: The original question has the counterexample of the convex drawing of $K_4$ as was pointed out in an answer. Moreover, I found some related counter-examples with a triangular border. I refined the question to reflect these, and added the condition of $3$-connectedness to avoid degenerate counterexamples as well.

Edit: reflected the path length to be calculated from the plane metric. Here is an example of a shorter path for the standard net of the cube.The red path is shorter than either component of the boundary

Edit 2: Following @IlyaBogdanov's suggestion in the comments, I tried a variation of the net of the cube. Assuming that the outer square has side $1$, the length of the red path is then $2\cos\alpha$, which can come arbitrarily close to $2$, but still comes short.enter image description here

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I'm not sure I understand the question. What is wrong with the standard drawing of a cube? $\endgroup$
    – Brendan McKay
    Commented May 4 at 9:14
  • $\begingroup$ @BrendanMcKay The standard drawing of a cube does have a shorter path. I might know why you think it is a counter example: I didn’t precise that the length of a path is the length induced from the plane, and not the usual graph edge counting. I will add this. $\endgroup$
    – Denis Gorodkov
    Commented May 4 at 13:01
  • 1
    $\begingroup$ It seems that, if you rotate the inner square by almost $\pi/2$, you get a counterexample. $\endgroup$
    – Ilya Bogdanov
    Commented May 6 at 8:37
  • $\begingroup$ @IlyaBogdanov Doesn't this break face convexity? I was able to get a path arbitrarily close to $2$ this way, but never greater than $2$ without breaking face convexity. I will add a picture to the question to reflect your comment, because it shows an example where the shortest path goes "backwards" from the target vertex. $\endgroup$
    – Denis Gorodkov
    Commented May 6 at 17:50
  • $\begingroup$ Ah, sorry, I missed the convexity condition! Then it looks more plausible. $\endgroup$
    – Ilya Bogdanov
    Commented May 8 at 8:49

2 Answers 2

Reset to default
1
$\begingroup$

What if we double one vertex in $K_4$, as in the picture?enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ This example, unfortunately, works! Great find (even if I expected a more complicated example). I think I could try to refine the question to remove these nearly triangular border polygons, but I shouldn't abuse the power to edit questions, so I will duly mark your answer as accepted, and rethink of a better way to ask the question. Thank you! $\endgroup$
    – Denis Gorodkov
    Commented May 9 at 1:12
1
$\begingroup$

Isn't the usual convex drawing of $K_4$ a counterexample?

Improve this answer
$\endgroup$
1
  • $\begingroup$ You are right: I was thinking about bigger examples (and those are the ones that I am interested in), and I missed to add such a restriction. I will edit the question to reflect this. Thank you! $\endgroup$
    – Denis Gorodkov
    Commented May 2 at 15:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .