Return to Question

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.

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.

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.

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.

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.

Consider a 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 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.

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.