Optimal grid drawings of complete multipartite graphs and an integer variant of the algebraic connectivity

Inicio | ¿Qué es? | Contacto

English | Català

Consultar RECERCAT

Por comunidades y
colecciones Por fecha Por autores Por títulos Por temas (CDU)

Consultar departamento

Por fecha Por autores Por títulos Por temas (CDU)

Estadisticas

Del documento Todo RECERCAT

Mi RECERCAT

Entrar Alertas por correo-e

Directorio de otros repositorios

RECERCAT Principal > Universitat Politècnica de Catalunya > Documents de recerca > Visualizar documento

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/129724

dc.contributor	Universitat Politècnica de Catalunya. Departament de Matemàtiques
dc.contributor	Universitat Politècnica de Catalunya. DCG - Discrete and Combinatorial Geometry
dc.contributor.author	Fabila Monroy, Ruy
dc.contributor.author	Hidalgo Toscano, Carlos
dc.contributor.author	Huemer, Clemens
dc.contributor.author	Lara, Dolores
dc.contributor.author	Mitsche, Dieter
dc.date	2018
dc.identifier.citation	Fabila, R. [et al.]. Optimal grid drawings of complete multipartite graphs and an integer variant of the algebraic connectivity. A: International Symposium on Graph Drawing and Network Visualization. "Graph Drawing and Network Visualization: 26th International Symposium, GD 2018, Barcelona, Spain, September 26-28, 2018: proceedings". Cham: Springer, 2018, p. 593-605.
dc.identifier.citation	978-3-030-04413-8
dc.identifier.citation	https://arxiv.org/pdf/1808.09024.pdf
dc.identifier.citation	10.1007/978-3-030-04414-5_42
dc.identifier.uri	http://hdl.handle.net/2117/129724
dc.language.iso	eng
dc.publisher	Springer
dc.relation	https://link.springer.com/book/10.1007/978-3-030-04414-5
dc.relation	info:eu-repo/grantAgreement/EC/H2020/734922/EU/Combinatorics of Networks and Computation/CONNECT
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs
dc.subject	Graph theory
dc.subject	multipartite graph
dc.subject	algebraic connectivity
dc.subject	Voronoi diagram
dc.subject	grid drawing
dc.subject	Grafs, Teoria de
dc.title	Optimal grid drawings of complete multipartite graphs and an integer variant of the algebraic connectivity
dc.type	info:eu-repo/semantics/submittedVersion
dc.type	info:eu-repo/semantics/conferenceObject
dc.description.abstract	How to draw the vertices of a complete multipartite graph G on different points of a bounded d-dimensional integer grid, such that the sum of squared distances between vertices of G is (i) minimized or (ii) maximized? For both problems we provide a characterization of the solutions. For the particular case d = 1, our solution for (i) also settles the minimum-2-sum problem for complete bipartite graphs; the minimum2-sum problem was defined by Juvan and Mohar in 1992. Weighted centroidal Voronoi tessellations are the solution for (ii). Such drawings are related with Laplacian eigenvalues of graphs. This motivates us to study which properties of the algebraic connectivity of graphs carry over to the restricted setting of drawings of graphs with integer coordinates.

Mostrar el registro sencillo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

The connectivity of the flip graph of Hamiltonian paths of the grid graph

Duque, Frank; Fabila Monroy, Ruy; Flores Peñazola, David; Hidalgo Toscano, Carlos; Huemer, Clemens

Empty non-convex and convex four-gons in random point sets

Fabila Monroy, Ruy; Huemer, Clemens; Mitsche, Dieter

Coloring decompositions of complete geometric graphs

Huemer, Clemens; Lara, Dolores; Rubio-Montiel, Christian

The number of empty four-gons in random point sets

Fabila-Monroy, Ruy; Huemer, Clemens; Mitsche, Dieter

On k-gons and k-holes in point sets

Aichholzer, Oswin; Fabila Monroy, Ruy; Gonzalez Aguilar, Hernan; Hackl, Thomas; Heredia, Marco A.; Huemer, Clemens; Urrutia Galicia, Jorge; Valtr, Pavel; Vogtenhuber, Birgit

Accesibilidad | Aviso legal | Política de Cookies | Documentos de uso interno

Coordinación

Patrocinio