Testing whether a subgraph is convex or isometricCabello, Sergio (Avtor) convex subgraphsisometric subgraphsplane graphsWe consider the following two algorithmic problems: given a graph $G$ and a subgraph $H\subseteq G$, decide whether $H$ is an isometric or a geodesically convex subgraph of $G$. It is relatively easy to see that the problems can be solved by computing the distances between all pairs of vertices. We provide a conditional lower bound showing that, for sparse graphs with $n$ vertices and $\Theta(n)$ edges, we cannot expect to solve the problem in $O(n^{2-\varepsilon})$ time for any constant $\varepsilon>0$. We also show that the problem can be solved in subquadratic time for planar graphs and in near-linear time for graphs of bounded treewidth. Finally, we provide a near-linear time algorithm for the setting where $G$ is a plane graph and $H$ is defined by a few cycles in $G$.20252025-12-16 12:35:42Članek v reviji176951UDK: 004.42:519.17DOI: 10.4230/LIPIcs.WADS.2025.12COBISS_ID: 261640963OceCobissID: 261608451sl