2 Search Results for "Resende, Mauricio G.C."

Document
DOI: 10.4230/LIPIcs.GD.2025.35
A Walk on the Wild Side: A Shape-First Methodology for Orthogonal Drawings

Authors: Giordano Andreola, Susanna Caroppo, Giuseppe Di Battista, Fabrizio Grosso, Maurizio Patrignani, and Allegra Strippoli

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
Several algorithms for the construction of orthogonal drawings of graphs, including those based on the Topology-Shape-Metrics (TSM) paradigm, tend to prioritize the minimization of crossings. This emphasis has two notable side effects: some edges are drawn with unnecessarily long sequences of segments and bends, and the overall drawing area may become excessively large. As a result, the produced drawings often lack geometric uniformity. Moreover, orthogonal crossings are known to have a limited impact on readability, suggesting that crossing minimization may not always be the optimal goal. In this paper, we introduce a methodology that "subverts" the traditional TSM pipeline by focusing on minimizing bends. Given a graph G, we ideally seek to construct a rectilinear drawing of G, that is, an orthogonal drawing with no bends. When not possible, we incrementally subdivide the edges of G by introducing dummy vertices that will (possibly) correspond to bends in the final drawing. This process continues until a rectilinear drawing of a subdivision of the graph is found, after which the final coordinates are computed. We tackle the (NP-complete) rectilinear drawability problem by encoding it as a SAT formula and solving it with state-of-the-art SAT solvers. If the SAT formula is unsatisfiable, we use the solver’s proof to determine which edge to subdivide. Our implementation, domus, which is fairly simple, is evaluated through extensive experiments on small- to medium-sized graphs. The results show that it consistently outperforms ogdf’s TSM-based approach across most standard graph drawing metrics.
Cite as

Giordano Andreola, Susanna Caroppo, Giuseppe Di Battista, Fabrizio Grosso, Maurizio Patrignani, and Allegra Strippoli. A Walk on the Wild Side: A Shape-First Methodology for Orthogonal Drawings. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{andreola_et_al:LIPIcs.GD.2025.35,
  author =	{Andreola, Giordano and Caroppo, Susanna and Di Battista, Giuseppe and Grosso, Fabrizio and Patrignani, Maurizio and Strippoli, Allegra},
  title =	{{A Walk on the Wild Side: A Shape-First Methodology for Orthogonal Drawings}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{35:1--35:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.35},
  URN =		{urn:nbn:de:0030-drops-250218},
  doi =		{10.4230/LIPIcs.GD.2025.35},
  annote =	{Keywords: Non-planar Orthogonal Drawings, SAT Solver, Experimental Comparison}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.45
A Local Search Algorithm for Large Maximum Weight Independent Set Problems

Authors: Yuanyuan Dong, Andrew V. Goldberg, Alexander Noe, Nikos Parotsidis, Mauricio G.C. Resende, and Quico Spaen

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Motivated by a real-world vehicle routing application, we consider the maximum-weight independent set problem: Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs arising in the vehicle routing application are large, having hundreds of thousands of nodes and hundreds of millions of edges. To solve instances of this size, we develop a new local search algorithm, which is a metaheuristic based on the greedy randomized adaptive search (GRASP) framework. This algorithm, named METAMIS, uses a wider range of simple local search operations than previously described in the literature. We introduce data structures that make these operations efficient. A new variant of path-relinking is introduced to escape local optima and so is a new alternating augmenting-path local search move that improves algorithm performance. We compare an implementation of our algorithm with a state-of-the-art publicly available code on public benchmark sets, including some large instances. Our algorithm is, in general, competitive and outperforms this openly available code on large vehicle routing instances of the maximum weight independent set problem. We hope that our results will lead to even better maximum-weight independent set algorithms.
Cite as

Yuanyuan Dong, Andrew V. Goldberg, Alexander Noe, Nikos Parotsidis, Mauricio G.C. Resende, and Quico Spaen. A Local Search Algorithm for Large Maximum Weight Independent Set Problems. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dong_et_al:LIPIcs.ESA.2022.45,
  author =	{Dong, Yuanyuan and Goldberg, Andrew V. and Noe, Alexander and Parotsidis, Nikos and Resende, Mauricio G.C. and Spaen, Quico},
  title =	{{A Local Search Algorithm for Large Maximum Weight Independent Set Problems}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{45:1--45:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.45},
  URN =		{urn:nbn:de:0030-drops-169839},
  doi =		{10.4230/LIPIcs.ESA.2022.45},
  annote =	{Keywords: GRASP, local search, maximum-weight independent set, path-relinking, heuristic, metaheuristic}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2022

  • Refine by Author
  • 1 Andreola, Giordano
  • 1 Caroppo, Susanna
  • 1 Di Battista, Giuseppe
  • 1 Dong, Yuanyuan
  • 1 Goldberg, Andrew V.
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Experimental Comparison
  • 1 GRASP
  • 1 Non-planar Orthogonal Drawings
  • 1 SAT Solver
  • 1 heuristic
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact