24,369 research outputs found
Two-Page Book Embeddings of 4-Planar Graphs
Get PDFBack in the eighties, Heath showed that every 3-planar graph is subhamiltonian and asked whether this result can be extended to a class of graphs of degree greater than three. In this paper we affirmatively answer this question for the class of 4-planar graphs. Our contribution consists of two algorithms: The first one is limited to triconnected graphs, but runs in linear time and uses existing methods for computing hamiltonian cycles in planar graphs. The second one, which solves the general case of the problem, is a quadratic-time algorithm based on the book embedding viewpoint of the problem
Bitonic st-orderings for Upward Planar Graphs
Get PDFCanonical orderings serve as the basis for many incremental planar drawing algorithms. All these techniques, however, have in common that they are limited to undirected graphs. While st-orderings do extend to directed graphs, especially planar st-graphs, they do not offer the same properties as canonical orderings. In this work we extend the so called bitonic st-orderings to directed graphs. We fully characterize planar st-graphs that admit such an ordering and provide a linear-time algorithm for recognition and ordering. If for a graph no bitonic st-ordering exists, we show how to find in linear time a minimum set of edges to split such that the resulting graph admits one. With this new technique we are able to draw every upward planar graph on n vertices by using at most one bend per edge, at most n−3 bends in total and within quadratic area
Recognizing Map Graphs of Bounded Treewidth
Get PDFA map graph is one admitting a representation in which vertices are nations on a spherical map and edges are shared curve segments or points between nations. We present an explicit fixed-parameter tractable algorithm for recognizing map graphs parameterized by treewidth. The algorithm has time complexity that is linear in the size of the graph and, if the input is a yes-instance, it reports a certificate in the form of a so-called witness. Furthermore, this result is developed within a more general algorithmic framework that allows to test, for any k, if the input graph admits a k-map (where at most k nations meet at a common point) or a hole-free k-map (where each point is covered by at least one nation). We point out that, although bounding the treewidth of the input graph also bounds the size of its largest clique, the latter alone does not seem to be a strong enough structural limitation to obtain an efficient time complexity. In fact, while the largest clique in a k-map graph is ⌊ 3k/2 ⌋, the recognition of k-map graphs is still open for any fixed k ≥ 5
MolMap - Visualizing Molecule Libraries as Topographic Maps
Get PDFWe present a new application for graph drawing and visualization in the context of drug discovery. Combining the scaffold-based cluster hierarchy with molecular similarity graphs — both standard concepts in cheminfor- matics — allows one to get new insights for analyzing large molecule libraries. The derived clustered graphs represent different aspects of structural similarity. We suggest visualizing them as topographic maps. Since the cluster hierarchy does not reflect the underlying graph structure as in (Gronemann and Jünger, 2012), we suggest a new partitioning algorithm that takes the edges of the graph into account. Experiments show that the new algorithm leads to significant improvements in terms of the edge lengths in the obtained drawings
Jack Alive / Martin Dead : The Location of the "Author" in Jack London\u27s Martin Eden
No full textThis essay is an attempt to read Martin Eden, Jack Londonʼs autobiographical novel, in terms of the inextricable relationship between the author and the protagonist. Critics have often taken the unbalanced plot and the lack of ironic distance between narrator and character in Martin Eden as the technical weakness of London, but this paper argues that the achievement of this novel owes a great deal to the attachment of London to Martin. The unbalanced structure is a necessary product of the severe struggle of the author to kill his romantic alter ego. // Martin, who aspires to win Ruth Morse, tries to cross class boundaries by making a career of a writer. Even after realizing the emptiness of Ruth, who turns out to be nothing but a typical figure of the bourgeoisie, he somehow persists in loving her. The notion underlying here is that, for Martin, love, career and art are fundamentally inseparable. He objects to the aestheteʼs view of Brissenden on account of his separation of art from career. Martinʼs identity and life consist only in the triunity of love/career/art; the alternative is the repudiation of life. Thus, the unnatural delay of his disappointment in love can be regarded as Londonʼs strategy to set the suicide of Martin as the necessary consequence of the story. // By finishing the story and killing Martin, London finally detaches himself from Martin, reconstructs his self, and, unlike Martin, survives as a professional writer. In this sense, Martin Eden is a story about “writerʼs self-reconstruction.
Recommended from our members
Letter from Martin Chizzick
No full textCongratulations to Duane Pearsall for receiving the Enterpreneur of the Year award; note on the letter was written by Pearsall and it mentions that Martin, the author of the letter, died in a airplane accident
Robert Martin Tiffin's Mystery Man Newspaper Articles
No full textAdvertiser-Tribune newspaper clippings featuring a story about Robert Martin (written by Nancy Kleinhenz), a local author from Tiffin (Ohio) who wrote under the pseudonym of Lee Roberts, and two of his short stories. Martin wrote mystery novels in his spare time, creating more than 22 mystery novels. For more information about Robert Martin and a list of books go to http://www.mysteryfile.com/RMartin/JBennett.html
Recognizing Map Graphs of Bounded Treewidth
No full textA map is a partition of the sphere into interior-disjoint regions homeomorphic to closed disks. Some regions are labeled as nations, while the remaining ones are labeled as holes. A map in which at most k nations touch at the same point is a k-map, while it is hole-free if it contains no holes. A graph is a map graph if there is a bijection between its vertices and the nations of a map, such that two nations touch if and only the corresponding vertices are connected by an edge. We present a fixed-parameter tractable algorithm for recognizing map graphs parameterized by treewidth. Its time complexity is linear in the size of the graph. It reports a certificate in the form of a so-called witness, if the input is a yes-instance. Our algorithmic framework is general enough to test, for any k, if the input graph admits a k-map or a hole-free k-map
Book embeddings of k-framed graphs and k-map graphs
No full textAn embedding of a graph in a book, called book embedding, consists of a linear ordering of its vertices along the spine of the book and an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. For planar graphs, a fundamental result is due to Yannakakis, who proposed an algorithm to compute embeddings of planar graphs in books with four pages. Our main contribution is a technique that generalizes this result to a much wider family of nonplanar graphs, namely to k-map graphs. In fact, our technique can deal with any nonplanar graph having a biconnected skeleton of crossingfree edges whose faces have bounded degree. We prove that this family of graphs has book thickness bounded in k, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal 2-planar graphs. (c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/)
Experiences Using Large Scale Video Walls for Distance Education
No full textWe describe our experiences building and using the Rutgers Videowall, a low-cost telepresence system that has been used teaching 15 courses and colloquia. By relaxing typical spatial telepresence features, such as background continuity, we greatly reduced costs and gained flexibility in the rooms it could be deployed in. The lower costs and room flexibility enabled academic departments to use the wall, in contrast to traditional telepresence systems which remained inaccessible. We found that the Videowall’s spatial distortions did not have a significant impact on useability, as our initial survey results show that students had an overall positive experience.Technical report DCS-tr-72
- …
