Information Technology Reference
In-Depth Information
In the full version of the paper, we prove that certain circle packings also cannot
be constructed by radical computation trees nor by bounded-degree root computation
trees.
6Con lu ion
We have shown that several types of graph drawing cannot be constructed by models
of computation that allow computation of arbitrary-degree radicals, nor by models that
allow computation of the roots of bounded-degree polynomials. Whether the degree of
these polynomials must grow linearly as a function of the input size, or only propor-
tionally to a sublinear power, remains subject to an open number-theoretic conjecture.
It is natural to ask whether these drawingsmight be computable in a model of
computation that allows both arbitrary-degree radicals and bounded-degree roots. We
leave this as open for future research.
Acknowledgements. We used the Sage software package to perform preliminary cal-
culations of the Galois groups of many drawings. Additionally, we thank Ricky Demer
on MathOverflow for guidingus to research on large factors of ˆ ( n ).
References
[1] Chrobak, M., Goodrich, M.T., Tamassia, R.: Convex drawingsofgraphs in two and three
dimensions. In: 12th Symp. on Computational Geometry (SoCG), pp. 319-328 (1996)
[2] Hopcroft, J.E., Kahn, P.J.: A paradigmforrobust geometric algorithms. Algorithmica 7,
339-380 (1992)
[3] Tutte, W.T.: How to draw a graph. Proc. London Math. Soc. 3, 743-767 (1963)
[4] Fruchterman,
T.M.J.,
Reingold,
E.M.:
Graph
drawing by
force-directed
placement.
Software: Practice and Experience 21, 1129-1164 (1991)
[5] Kamada, T., Kawai, S.: An algorithm for drawinggeneral undirected graphs. Information
Processing Letters 31, 7-15 (1989)
[6] Koren, Y.: Drawinggraphs by eigenvectors: theory and practice. Computers & Mathematics
with Applications 49, 1867-1888 (2005)
[7] Kruskal, J.B., Seery, J.B.: Designing network diagrams. In: Proc. First General Conf. on
Social Graphics, pp. 22-50 (1980)
[8] Koebe, P.: Kontaktprobleme der Konformen Abbildung.Ber.Sachs. Akad. Wiss. Leipzig,
Math.-Phys. Kl. 88, 141-164 (1936)
[9] Bajaj, C.: The algebraic complexity of shortest paths in polyhedral spaces. In: Proc. 23rd
Allerton Conf. on Communication, Control and Computing, pp. 510-517 (1985)
[10] Carufel, J.L.D., Grimm, C., Maheshwari, A., Owen, M., Smid, M.: A Note on the
unsolvability of the weighted region shortest path problem. In: Booklet of Abstracts of the
28th European Workshop on Computational Geometry, pp. 65-68 (2013)
[11] Bajaj, C.: The algebraic degree of geometric optimization problems. Discrete Comput.
Geom. 3, 177-191 (1988)
[12] Nister, D., Hartley, R., Stewenius, H.: Using Galois theory to prove structure from motion
algorithms are optimal. In: IEEE Conf. Computer Vision & Pattern Recog., pp. 1-8 (2007)
[13] Varfolomeev, V.V.: Galois groups of the Heron-Sabitov polynomials for inscribed
pentagons. Mat. Sb. 195, 3-16 (2004); Translation in Sb. Math. 195, 149-162 (2004)
Search WWH ::




Custom Search