Drawing Graphs with Vertices and Edges in Convex Position

García-Marco, Ignacio and Knauer, Kolja (2015) Drawing Graphs with Vertices and Edges in Convex Position. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 348-359 (Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_29).

Full text not available from this repository.


A graph has strong convex dimension 2, if it admits a straight-line drawing in the plane such that its vertices are in convex position and the midpoints of its edges are also in convex position. Halman, Onn, and Rothblum conjectured that graphs of strong convex dimension 2 are planar and therefore have at most 3n−6 edges. We prove that all such graphs have at most 2n−3 edges while on the other hand we present a class of non-planar graphs of strong convex dimension 2. We also give lower bounds on the maximum number of edges a graph of strong convex dimension 2 can have and discuss variants of this graph class. We apply our results to questions about large convexly independent sets in Minkowski sums of planar point sets, that have been of interest in recent years.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.490 Embeddings
P Styles > P.720 Straight-line
P Styles > P.999 Others
Z Theory > Z.750 Topology
ID Code:1501

Repository Staff Only: item control page


Bílka, O., Buchin, K., Fulek, R., Kiyomi, M., Okamoto, Y., Tanigawa, S., Tóth, C.D.: A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets. Electron. J. Combin. 17(1), Note 35, 4 (2010)

Eisenbrand, F., Pach, J., Rothvoß, T., Sopher, N.B.: Convexly independent subsets of the Minkowski sum of planar point sets, Electron. J. Combin. 15(1), Note 8, 4 (2008)

Halman, N., Onn, S., Rothblum, U.G.: The convex dimension of a graph. Discrete Appl. Math. 155(11), 1373–1383 (2007)

Onn, S., Rothblum, U.G.: Convex combinatorial optimization. Discrete Comput. Geom. 32(4), 549–566 (2004)

Swanepoel, K.J., Valtr, P.: Large convexly independent subsets of Minkowski sums. Electron. J. Combin. 17(1) (2010). Research Paper 146, 7

Hans Raj Tiwary: On the largest convex subsets in Minkowski sums. Inf. Process. Lett. 114(8), 405–407 (2014)