Abstract
Motivated by the study of ordinal embeddings in machine learning and by the recognition of Euclidean preferences in computational social science, we study the following problem. Given a graph G, together with a set of relationships between pairs of edges, each specifying that an edge must be longer than another edge, is it possible to construct a straight-line drawing of G satisfying all these relationships?
We mainly consider a dichotomous setting, in which edges are partitioned into short and long, as otherwise there are simple (planar) instances that do not admit a solution. Since the problem is NP-hard even in this setting, we study under which conditions a solution always exists. We prove that degeneracy-2 graphs, subcubic graphs, double-wheels, and 4-colorable graphs in which the short edges induce a caterpillar always admit a realization. These positive results are complemented by negative instances, even when the input graph is composed of a maximal planar graph, namely a double-wheel graph, and an edge. We conjecture that planar graphs always admit a (not necessarily planar) realization in the dichotomous setting.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agarwal, S., Wills, J., Cayton, L., Lanckriet, G.R.G., Kriegman, D.J., Belongie, S.J.: Generalized non-metric multidimensional scaling. In: Meila, M., Shen, X. (eds.) AISTATS. JMLR Proceedings, vol. 2, pp. 11–18. JMLR.org (2007)
Aichholzer, O., Hoffmann, M., van Kreveld, M.J., Rote, G.: Graph drawings with relative edge length specifications. In: CCCG (2014)
Ailon, N.: An active learning algorithm for ranking from pairwise preferences with an almost optimal query complexity. J. Mach. Learn. Res. 13, 137–164 (2012)
Alam, M.J., Kobourov, S.G., Pupyrev, S., Toeniskoetter, J.: Weak unit disk and interval representation of graphs. In: Mayr, E.W. (ed.) WG 2015. LNCS, vol. 9224, pp. 237–251. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53174-7_17
Alon, N., Badoiu, M., Demaine, E.D., Farach-Colton, M., Hajiaghayi, M.T., Sidiropoulos, A.: Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics. ACM Trans. Algorithms 4(4), 46:1–46:21 (2008)
Bennett, J.F., Hays, W.L.: Multidimensional unfolding: determining the dimensionality of ranked preference data. Psychometrika 25(1), 27–43 (1960)
Borg, I., Groenen, P.: Modern Multidimensional Scaling: Theory and Applications. Springer, Heidelberg (2005)
Cabello, S., Demaine, E.D., Rote, G.: Planar embeddings of graphs with specified edge lengths. J. Graph Algorithms Appl. 11(1), 259–276 (2007)
Chen, J., Pruhs, K., Woeginger, G.J.: The one-dimensional Euclidean domain: finitely many obstructions are not enough. Soc. Choice Welf. 48(2), 409–432 (2017)
Doignon, J., Falmagne, J.: A polynomial time algorithm for unidimensional unfolding representations. J. Algorithms 16(2), 218–233 (1994)
Eades, P., Wormald, N.C.: Fixed edge-length graph drawing is NP-hard. Discret. Appl. Math. 28(2), 111–134 (1990)
Elkind, E., Lackner, M.: Structure in dichotomous preferences. In: Yang, Q., Wooldridge, M. (eds.) IJCAI, pp. 2019–2025. AAAI Press (2015)
Jamieson, K.G., Nowak, R.D.: Low-dimensional embedding using adaptively selected ordinal data. In: Allerton Conference on Communication, Control, and Computer, pp. 1077–1084. IEEE (2011)
Kruskal, J.: Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika 29(1), 1–27 (1964)
Kruskal, J.: Nonmetric multidimensional scaling: a numerical method. Psychometrika 29(2), 115–129 (1964)
Peters, D.: Recognising multidimensional Euclidean preferences. In: Singh, S.P., Markovitch, S. (eds.) AAAI, pp. 642–648. AAAI Press (2017)
Quist, M., Yona, G., Yu, B.: Distributional scaling: an algorithm for structure-preserving embedding of metric and nonmetric spaces. J. Mach. Learn. Res. 5, 399–420 (2004)
Saxe, J.B.: Embeddability of weighted graphs in \(k\)-space is strongly NP-hard. In: 17th Allerton Conference on Communication, Control, and Computer, pp. 480–489. IEEE (1979)
Shepard, R.N.: The analysis of proximities: multidimensional scaling with an unknown distance function. I. Psychometrika 27(2), 125–140 (1962)
Shepard, R.N.: The analysis of proximities: multidimensional scaling with an unknown distance function. II. Psychometrika 27(3), 219–246 (1962)
Terada, Y., von Luxburg, U.: Local ordinal embedding. In: ICML. JMLR Workshop and Conference Proceedings, vol. 32, pp. 847–855. JMLR.org (2014)
Vo, D., Vo, N., Challa, S.: Weighted MDS for Sensor Localization. In: Gervasi, O., Murgante, B., Laganà, A., Taniar, D., Mun, Y., Gavrilova, M.L. (eds.) ICCSA 2008. LNCS, vol. 5073, pp. 409–418. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-69848-7_34
Acknowledgement
The authors would like to thank Michael Kaufmann and Ulrike von Luxburg for useful discussions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Angelini, P., Bekos, M.A., Gronemann, M., Symvonis, A. (2019). Geometric Representations of Dichotomous Ordinal Data. In: Sau, I., Thilikos, D. (eds) Graph-Theoretic Concepts in Computer Science. WG 2019. Lecture Notes in Computer Science(), vol 11789. Springer, Cham. https://doi.org/10.1007/978-3-030-30786-8_16
Download citation
DOI: https://doi.org/10.1007/978-3-030-30786-8_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-30785-1
Online ISBN: 978-3-030-30786-8
eBook Packages: Computer ScienceComputer Science (R0)