A conforming partition of a rectilinear n -gon P (possibly with holes) is a partition of P into rectangles without using Steiner points (i.e., all corners of all rectangles must lie on the boundary of P ). The stabbing number of such a partition is the maximum number of rectangles intersected by an axis-aligned segment lying in the interior of P . In this paper, we examine the problem of computing conforming partitions with low stabbing number. We show that computing a conforming partition with stabbing number at most 4 is NP -hard, which strengthens a previously known hardness result [Durocher & Mehrabi, Theor. Comput. Sci. 689: 157-168 (2017)] and eliminates the possibility for fixed-parameter-tractable algorithms parameterized by the stabbing number unless P = NP . In contrast, we give (i) an O ( n log ⁡ n ) -time algorithm to decide whether a conforming partition with stabbing number 2 exists, (ii) a fixed-parameter-tractable algorithm parameterized by both the stabbing number and treewidth of the pixel graph of the polygon, and (iii) a fixed-parameter-tractable algorithm parameterized by the stabbing number for polygons without holes in general position.

A disk graph is an intersection graph of disks in $\mathbb{R}^2$. Determining the computational complexity of finding a maximum clique in a disk graph is a long-standing open problem. In 1990, Clark, Colbourn, and Johnson gave a polynomial-time algorithm for computing a maximum clique in a unit disk graph. However, finding a maximum clique when disks are of arbitrary size is widely believed to be a challenging open problem. The problem is open even if we restrict the disks to have at most two different sizes of radii, or restrict the radii to be within $[1,1+\varepsilon]$ for some $ε>0$. In this paper, we provide a new perspective to examine adjacencies in a disk graph that helps obtain the following results. - We design an $O(2^k n^{2k} poly(n))$-time algorithm to find a maximum clique in a $n$-vertex disk graph with $k$ different sizes of radii. This is polynomial for every fixed $k$, and thus settles the open question for the case when $k=2$. - Given a set of $n$ unit disks, we show how to compute a maximum clique inside each possible axis-aligned rectangle determined by the disk centers in $O(n^5\log n)$-time. This is at least a factor of $n^{4/3}$ faster than applying the fastest known algorithm for finding a maximum clique in a unit disk graph for each rectangle independently. - We give an $O(2^kn^{2rk} poly(n,r))$-time algorithm to find a maximum clique in a $n$-vertex ball graph with $k$ different sizes of radii where the ball centers lie on $r$ parallel planes. This is polynomial for every fixed $k$ and $r$, and thus contrasts the previously known NP-hardness result for finding a maximum clique in an arbitrary ball graph.

This report describes the 32nd Annual Graph Drawing Contest, held in conjunction with the 33rd International Symposium on Graph Drawing and Network Visualization (GD'25) at Linköping University, Norrköping, Sweden. The mission of the Graph Drawing Contest is to monitor and challenge the current state of the art in graph-drawing technology. This year’s edition featured two categories, a creative topic in which participants visualized a dataset based on the Netflix show Dark and a live challenge held at the conference where participants had to draw a graph on a grid, such that the drawing is k-planar for as low a k as possible. A special feature of this year’s contest is that the submissions to the creative topic were exhibited in the "Norrköping Decision Arena", a room with a circular annulus-shaped screen.

A k-layer polyline drawing of a planar graph G is a planar drawing of G on a set L of k parallel lines such that each vertex is mapped to a point on L and each edge is mapped to a polygonal chain with the endpoints and bends lying on L. In the fixed embedding setting, the output drawing maintains the given planar embedding, whereas in the variable embedding setting, the embedding may change. Every n-vertex planar graph admits a polyline drawing on 2n/3 layers, which is the best known upper bound for both settings. We improve this bound in the variable embedding setting. We show that every planar graph can be drawn on 14n/27+O(√n) layers by choosing a proper planar embedding, breaking the long-standing 2n/3-layer barrier.

A map visualization of a graph consists of a node-link diagram in which groups of nodes are enclosed in one or more polygonal regions, similar to countries in a geographic map. Many real-world graphs have naturally defined groups, e.g., a graph that represents collaborations between faculty members within a university, where the departments are the groups. A good visualization of such a graph should place departments that collaborate frequently as adjacent or nearby groups. While some set visualization methods can be used to create map visualizations for graphs with groups, the results can be poor and difficult to read due to fragmented groups or complicated polygonal shapes of the enclosing regions. With this in mind, we propose a new approach that constructs the polygons first and then renders the graph to obtain better control over the drawing properties. We design two methods based on this new approach and compare them with three prior techniques using seven quantitative metrics on several real-world datasets. Our experimental results demonstrate the proposed methods to outperform prior techniques in capturing the intended drawing features and have good performance in most of the metrics.

Node-link visualizations are commonly used to gain insights into large network data where the entities of the networks (nodes) are represented as points, and relationships (edges) are drawn as straight line segments or links. With growing access to network data and visualization tools, such visualizations are increasingly appearing in infographics and documents intended for non-specialist readers. This necessitates understanding how these visualizations are perceived by end users who are not necessarily domain experts, and determining how visual summaries can be provided to ensure consistent interpretation of the displayed information. In this paper, we investigate the interpretability of node-link visualizations of large graphs: we designed summary representations that could be provided alongside the visualization to improve interpretation, and we evaluated these designs through two user studies. Our results indicate that the information perceived from traditional node-link representations can vary substantially, especially when the nodes are uniformly distributed rather than forming clusters or tangled structures. We observed that visual summaries can enhance the readability of these visualizations – summaries that reduce clutter were preferred by participants and were more accurate for typical interpretation tasks.

Force-directed layouts are popular for graph visualization but often ignore edge direction, limiting their use for directed networks. Existing direction-aware methods apply global magnetic fields, revealing only broad hierarchical patterns. In this paper, we introduce a multi-pole magnetic force model that assigns localized polar fields to user-defined nodes ("poles"), attracting nearby nodes based on shortest-path distances. This approach reveals node-centric hierarchies influenced by the selected poles. We enhance traditional force-based algorithms by introducing pole gravity, pole separation, and circular hierarchy forces to improve the clarity of node-centric local structures. Experiments on citation, software, and Twitter networks show fewer edge crossings and misaligned edges, with clearer hierarchical structures than existing force-based methods, along with better quantitative performance metrics. Our technique is released as an open-source Cytoscape plugin ‘CodeNetVis’ for practical analysis of software dependency graphs.

Testing and debugging software to fix bugs is considered one of the most important stages of the software life cycle. Many studies have investigated ways to predict bugs in software artifacts using machine learning techniques. It is important to consider the explanatory aspects of such models for reliable prediction. In this paper, we show how feature transformation can significantly improve prediction accuracy and provide insight into the inner workings of bug prediction models. We propose a new approach for bug prediction that first extracts the features, then finds a weighted transformation of these features using a genetic algorithm that best separates bugs from non-bugs when plotted in a low-dimensional space, and finally, trains predictive models using the transformed dataset. In our experiment using the proposed feature transformation, the traditional machine learning and deep learning classifiers achieved an average improvement of 4.25% and 9.6% in recall values for bug classification over 8 software systems compared to the models built on original data. We also examined the generalizability of our concept for multiclass classification tasks such as commit classification in software systems and found modest improvements in F1-scores (sometimes up to 3%) for traditional machine learning models and 4% with deep learning models. • Feature transformation techniques applied to bug detection in software systems. • Genetic algorithm based transformation and t-SNE based clustering in low dimensions. • Improved explainability and accuracy of machine learning based bug detection models. • Applicable to deep learning models and generalizable to commit classification.

Given a set P of points and a set U of geometric objects in the Euclidean plane, a minimum ply cover of P with U is a subset of U that covers P and minimizes the number of objects that share a common intersection, called the minimum ply cover number of P with U . Biedl et al. (2021) [9] showed that for both unit squares and unit disks, determining the minimum ply cover number for a set of points is NP-hard. They gave polynomial-time 2-approximation algorithms for the special case when the minimum ply cover number is constant, and asked whether there exists polynomial-time O ( 1 ) -approximation algorithms for these problems. In this paper, we settle the question posed by Biedl et al. by providing polynomial-time O ( 1 ) -approximation algorithms for the minimum ply cover problem for both unit squares and unit disks.

Detecting and tracking code clones can ease various software development and maintenance tasks when changes in a code fragment should be propagated over all its copies. Several deep learning based clone detection models have appeared in the literature for detecting syntactic and semantic clones, and these models have widely been evaluated with the BigCloneBench dataset. However, the class imbalance and small number of semantic clones make BigCloneBench less ideal when interpreting the model performances. Sometimes researchers use a few other semantic clone datasets such as GoogleCodeJam, OJClone and SemanticCloneBench to understand a model's generalizability. To overcome the limitations of the existing datasets, recently a GPT-assisted large semantic and cross-language clone dataset GPT-CloneBench has been released, but it is not clear how all these models would compare and contrast in terms of these datasets. In this paper, we propose a multi-step evaluation approach for five state-of-the-art clone detection models leveraging existing bench-mark datasets including the recently proposed GPTCloneBench and exploiting the mutation operators to study the extent of these clone detection models' ability. More specifically, we examined the performance of three highly-performing single-language clone detection models (ASTNN, GMN, CodeBERT) that use various code representations (e.g., AST, flow augmented AST with graph matching network, and bidirectional encoder representation) for detecting semantic clones. In addition to using BigCloneBench, we tested them on SemanticCloneBench and GPTCloneBench, investigated their robustness under mutation operations, and examined them against cutting-edge cross-language clone detection tools (C4, CLCDSA) that are also known to learn semantic clones. While all single-language models showed high F1 scores for BigCloneBench, their performances varied quite differently (sometimes over 20%) when tested on SemanticCloneBench. Interestingly, the cross-language model (C4) consistently showed superior performance (around 7%) on SemanticCloneBench over other models and performed similarly for BigCloneBench and GPTCloneBench. On mutation-based datasets, C4 appeared to have a more robust performance (less than 1% difference) whereas single-language models showed high variability.

Choosing an appropriate software development technology (e.g., programming language) is challenging due to the proliferation of diverse options. The selection of inappropriate technologies for development may have a far-reaching effect on software developers' career growth. Switching to a different technology after working with one may lead to a complex learning curve and, thus, be more challenging. Therefore, it is crucial for software developers to find technologies that have a high usage span. Intuitively, the usage span of a technology can be deter-mined by the time span developers have used that technology. Existing literature focuses on the technology landscape to explore the complex and implicit dependencies among technologies but lacks formal studies to draw insights about their usage span. This paper investigates the technology usage span by analyzing the question and answering (Q&A) traces of Stack Overflow (SO), the largest technical Q&A website available to date. In particular, we analyze 6.7 million Q&A traces posted by about 97K active SO users and see what technologies have appeared in their questions or answers over 15 years. According to our analysis, C# and Java programming languages have a high usage span, followed by JavaScript. Besides, developers used the. NET framework, iO$S$& Windows Operating Systems (OS), and SQL query language for a long time (on average). Our study also exposes the emerging (i.e., newly growing) technologies. For example, usages of technologies such as SwiftUI,. NET-6.0, Visual Studio 2022, and Blazor WebAssembly framework are increasing. The findings from our study can assist novice developers, startup software industries, and software users in determining appropriate technologies. This also establishes an initial benchmark for future investigation on the use span of software technologies.

A disk graph is an intersection graph of disks in the Euclidean plane, where the disks correspond to the vertices of the graph and a pair of vertices are adjacent if and only if their corresponding disks intersect. The problem of determining the time complexity of computing a maximum clique in a disk graph is a long-standing open question that has been very well studied in the literature. The problem is known to be open even when the radii of all the disks are in the interval [1,(1+ε)], where ε > 0. If all the disks are unit disks then there exists an O(n³log n)-time algorithm to compute a maximum clique, which is the best-known running time for over a decade. Although the problem of computing a maximum clique in a disk graph remains open, it is known to be APX-hard for the intersection graphs of many other convex objects such as intersection graphs of ellipses, triangles, and a combination of unit disks and axis-parallel rectangles. Here we obtain the following results. - We give an algorithm to compute a maximum clique in a unit disk graph in O(n^2.5 log n)-time, which improves the previously best known running time of O(n³log n) [Eppstein '09]. - We extend a widely used "co-2-subdivision approach" to prove that computing a maximum clique in a combination of unit disks and axis-parallel rectangles is NP-hard to approximate within 4448/4449 ≈ 0.9997. The use of a "co-2-subdivision approach" was previously thought to be unlikely in this setting [Bonnet et al. '20]. Our result improves the previously known inapproximability factor of 7633010347/7633010348 ≈ 0.9999. - We show that the parameter minimum lens width of the disk arrangement may be used to make progress in the case when disk radii are in [1,(1+ε)]. For example, if the minimum lens width is at least 0.265 and ε ≤ 0.0001, which still allows for non-Helly triples in the arrangement, then one can find a maximum clique in polynomial time.

Modern Code Review (MCR) is an integral part of a software development strategy that accelerates product quality by identifying defects, code smells, and other harmful practices. However, assigning appropriate reviewers to evaluate changed code during the review process remains challenging. While automated tools for reviewer assignments have limited impact in practice, the process often relies on manual investigation of project histories to retrieve knowledge of team members and their activities. Therefore, in this study, we present an approach to automatically assemble developers’ information and visualize it meaningfully, which helps to choose appropriate reviewers. First, we propose three metrics that measure developers’ collaboration, reviewers’ expertise, and reviewers’ workload and visualize them through networks. Second, we perform a case study of three popular open-source projects, where we compute and visualize each developers’ information according to the proposed metrics. Finally, we conducted two online surveys to assess the developers’ perceptions of the proposed visual benefits. The results show that the proposed method can assist in identifying relevant reviewers and be immensely helpful to new developers. Additionally, survey respondents expressed reliance on the efficacy of the visual aids in workload balancing and reducing review time.

Software clones are often introduced when developers reuse code fragments to implement similar functionalities in the same or different software systems resulting in duplicated fragments or code clones in those systems. Due to the adverse effect of clones on software maintenance, a great many tools and techniques and techniques have appeared in the literature to detect clones. Many high-performing clone detection tools today are based on deep learning techniques and are mostly used for detecting clones written in the same programming language, whereas clone detection tools for detecting cross-language clones are also emerging rapidly. The popularity of deep learning-based clone detection tools creates an opportunity to investigate how known strategies that boost the performances of deep learning models could be further leveraged to improve the clone detection tools. In this paper, we investigate such a strategy, data augmentation, which has not yet been explored for cross-language clone detection as opposed to single language clone detection. We show how the existing knowledge on transcompilers (source-to-source translators) can be used for data augmentation to boost the performance of cross-language clone detection models, as well as to adapt single-language clone detection models to create cross-language clone detection pipelines. To demonstrate the performance boost for cross-language clone detection through data augmentation, we exploit Transcoder, which is a pre-trained source-to-source translator. To show how to extend single-language models for cross-language clone detection, we extend a popular single-language model, Graph Matching Network (GMN), in a combination with the transcompilers and code parsers (srcML). We evaluated our models on popular benchmark datasets. Our experimental results showed improvements in F1 scores (sometimes up to 3%) for the cutting-edge cross-language clone detection models. Even when extending GMN for cross-language clone detection, the models built leveraging data augmentation outperformed the baseline with scores of 0.90, 0.92, and 0.91 for precision, recall, and F1 score, respectively.

Multi-attribute dataset visualizations are often designed based on attribute types, i.e., whether the attributes are categorical or numerical. Parallel Sets and Parallel Coordinates are two well-known techniques to visualize categorical and numerical data, respectively. A common strategy to visualize mixed data is to use multiple information linked view, e.g., Parallel Coordinates are often augmented with maps to explore spatial data with numeric attributes. In this paper, we design visualizations for mixed data, where the dataset may include numerical, categorical, and spatial attributes. The proposed solution SET-STAT-MAP is a harmonious combination of three interactive components: Parallel Sets (visualizes sets determined by the combination of categories or numeric ranges), statistics columns (visualizes numerical summaries of the sets), and a geospatial map view (visualizes the spatial information). We augment these components with colors and textures to enhance users' capability of analyzing distributions of pairs of attribute combinations. To improve scalability, we merge the sets to limit the number of possible combinations to be rendered on the display. We demonstrate the use of Set-stat-map using two different types of datasets: a meteorological dataset and an online vacation rental dataset (Airbnb). To examine the potential of the system, we collaborated with the meteorologists, which revealed both challenges and opportunities for Set-stat-map to be used for real-life visual analytics.

A 2-interval is the union of two disjoint intervals on the real line. Two 2-intervals D1 and D2 are disjoint if their intersection is empty (i.e., no interval of D1 intersects any interval of D2). There can be three different relations between two disjoint 2-intervals; namely, preceding (<), nested (⊏) and crossing (≬). Two 2-intervals D1 and D2 are called R-comparable for some R∈{<,⊏,≬}, if either D1RD2 or D2RD1. A set D of disjoint 2-intervals is R-comparable, for some R⊆{<,⊏,≬} and R≠∅, if every pair of 2-intervals in D are R-comparable for some R∈R. Given a set of 2-intervals and some R⊆{<,⊏,≬}, the objective of the 2-interval pattern problem is to find a largest subset of 2-intervals that is R-comparable. The 2-interval pattern problem is known to be W[1]-hard when |R|=3 and NP-hard when |R|=2 (except for R={<,⊏}, which is solvable in quadratic time). In this paper, we fully settle the parameterized complexity of the problem by showing that it is W[1]-hard for both R={⊏,≬} and R={<,≬} (when parameterized by the size of an optimal solution). This answers the open question posed by Vialette ((2008) [22]).

Changes in spatiotemporal data may often go unnoticed due to their inherent noise and low variability (e.g., geological processes over years). Commonly used approaches such as side-by-side contour plots and spaghetti plots do not provide a clear idea about the temporal changes in such data. We propose ContourDiff, a vector-based visualization over contour plots to visualize the trends of change across spatial regions and temporal domain. Our approach first aggregates for each location, its value differences from the neighboring points over the temporal domain, and then creates a vector field representing the prominent changes. Finally, it overlays the vectors along the contour paths, revealing differential trends that the contour lines experienced over time. We evaluated our visualization using real-life datasets, consisting of millions of data points, where the visualizations were generated in less than a minute in a single-threaded execution. Our experimental results reveal that ContourDiff can reliably visualize the differential trends, and provide a new way to explore the change pattern in spatiotemporal data.

The storage, retrieval, and distribution of data are some critical aspects of big data management. Data scientists and decision-makers often need to share large datasets and make decisions on archiving or deleting historical data to cope with resource constraints. A potential approach to mitigate such problems is to reduce big datasets into smaller ones, which will not only lower storage requirements but also allow light load transfer over the network. Carefully prepared data by removing redundancies, along with a machine learning model capable of reconstructing the whole dataset from its reduced version, can improve the storage scalability, data transfer, and speed up the overall data management pipeline. In this paper, we explore some data reduction strategies for big datasets, while ensuring that the data can be transferred and used ubiquitously by all stakeholders, i.e., the entire dataset can be reconstructed with high quality whenever necessary. Our approach guarantees a minimum of 75% data size reduction, where the reconstruction accuracy observed is as high as 98.75% on an average for geospatial meteorological data (e.g., soil moisture and albedo), and 99.09% for satellite imagery. We propose a novel variance based reduction technique that can further reduce the data size without losing the accuracy significantly, and adopt various deep learning approaches for high-quality reconstruction.

Professional training often requires need-based scheduling and observation-based assessment. In this paper, we present a visualization platform for managing such training data in a medical education domain, where the learners are resident physicians and the educators are certified doctors. The system was developed through four focus groups with the residents and their educators over six major development iterations. We present how the professionals involved, nature of training, choice of the display devices, and the overall assessment process influenced the design of the visualizations. The final system was deployed as a web tool for the department of emergency medicine, and evaluated by both the residents and their educators in an uncontrolled longitudinal study. Our analysis of four months of user logs revealed interesting usage patterns consistent with real-life training events and showed an improvement in several key learning metrics when compared to historical values during the same study period. The users' feedback showed that both educators and residents found our system to be helpful in real-life decision making.

Abstract We introduce a problem called minimum shared‐power edge cut (MSPEC). The input to the problem is an undirected edge‐weighted graph with distinguished vertices s and t, and the goal is to find an s‐t cut by assigning “powers” at the vertices and removing an edge if the sum of the powers at its endpoints is at least its weight. The objective is to minimize the sum of the assigned powers. MSPEC is a graph generalization of a barrier coverage problem in a wireless sensor network: given a set of unit disks with centers in a rectangle, what is the minimum total amount by which we must shrink the disks to permit an intruder to cross the rectangle undetected, that is, without entering any disk. This is a more sophisticated measure of barrier coverage than the minimum number of disks whose removal breaks the barrier. We develop a fully polynomial time approximation scheme for MSPEC. We give polynomial time algorithms for the special cases where the edge weights are uniform, or the power values are restricted to a bounded set. Although MSPEC is related to network flow and matching problems, its computational complexity (in P or NP‐hard) remains open.

The information on a non-prescription (over-the-counter) medicine label helps patients to make informed decisions when purchasing a medicine. Since non-prescription medicines can be purchased without consulting a healthcare professional, there is a growing concern that people do not put enough emphasis on reading medicine label information, resulting in drug misuse with possible health consequences. In this paper, we investigate patients' use of medicine labels with the goal of developing a smartphone application to guide them toward reading the important information (e.g., warnings, dosage) on the labels. We first conducted two studies examining (i) users' rating on the information that they commonly read and (ii) healthcare professionals' rating on the information that patients should read before purchasing a non-prescription medicine. Our results revealed that patients put less emphasis on reading many information such as dosage, warnings and precautions, that the healthcare professions highly recommend the patients to read. Inspired by the findings, we designed a smartphone application to make users aware of the important information on non-prescription medicines. Along the way, we conduct a study examining different information presentation techniques to show medicine labels on smartphones, where our results show that icons and texts are more accurate and preferred techniques by users. In a further study where users explore medicines with our smartphone application, we observed a significant increase (mean 27%) in the general users' rating on the information categories that were recommended by healthcare professionals. This suggests that the users were guided to read important information by the smartphone application.

With the era of big data approaching, the number of software systems, their dependencies, as well as the complexity of the individual system is becoming larger and more intricate. Understanding these evolving software systems is thus a primary challenge for cost-effective software management and maintenance. In this paper we perform a case study with evolving code clones. The programmers often need to manually analyze the co-evolution of clone fragments to decide about refactoring, tracking, and bug removal. However, manual analysis is time consuming, and nearly infeasible for a large number of clones, e.g., with millions of similarity pairs, where clones are evolving over hundreds of software revisions. We propose an interactive visual analytics system, Clone-World , which leverages big data visualization approach to manage code clones in large software systems. Clone-World , gives an intuitive yet powerful solution to the clone analytic problems. Clone-World combines multiple information-linked zoomable views, where users can explore and analyze clones through interactive exploration in real time. User studies and experts’ reviews suggest that Clone-World may assist developers in many real-life software development and maintenance scenarios. We believe that Clone-World will ease the management and maintenance of clones, and inspire future innovation to adapt visual analytics to manage big software systems.

The thickness of a graph $G=(V,E)$ with $n$ vertices is the minimum number of planar subgraphs of $G$ whose union is $G$. A polyline drawing of $G$ in $\mathbb{R}^2$ is a drawing $\Gamma$ of $G$, where each vertex is mapped to a point and each edge is mapped to a polygonal chain between the corresponding endpoints. Bend and layer complexities are two important aesthetics of such a drawing. The bend complexity of $\Gamma$ is the maximum number of bends per edge in $\Gamma$, and the layer complexity of $\Gamma$ is the minimum integer $r$ such that the set of polygonal chains in $\Gamma$ can be partitioned into $r$ disjoint sets, where each set corresponds to a planar polyline drawing. Let $G$ be a graph of thickness $t$. By Fáry's theorem, if $t=1$, then $G$ can be drawn on a single layer with bend complexity $0$. A few extensions to higher thickness are known, e.g., if $t=2$ (resp., $t>2$), then $G$ can be drawn on $t$ planar layers with bend complexity 2 (resp., $3n+O(1)$). In this paper we present an elegant extension of Fáry's theorem to draw graphs of thickness $t>2$. We first prove that thickness-$t$ graphs can be drawn on $t$ planar layers with $2.25n+O(1)$ bends per edge. We then develop another technique to draw thickness-$t$ graphs on $t$ planar layers with bend complexity $O(\sqrt{2}^{t} \cdot n^{1-(1/\beta)})$, where $\beta = 2^{\lceil (t-2)/2 \rceil }$. If $t$ is fixed, then this gives a sublinear bound on the bend complexity. Previously, the bend complexity was not known to be sublinear for any $t>2$. Finally, we show that graphs with linear arboricity $k$ can be drawn on $k$ planar layers with bend complexity $\frac{3(k-1)n}{(4k-2)}$. Note that we do not compute the edge-partition of the given graph into $t$ planar subgraphs or into $k$ linear forests, but we assume that such a partition is given as an input to our algorithm.

Test case selection is a classic testing technique to choose a subset of existing test cases for execution, due to the limited budget and tight deadlines. While `code coverage' is the state of practice among test case selection heuristics, recent literature has shown that `test case diversity' is also a very promising approach. In this paper, we first compare these two heuristics for test case selection in several real-world case studies (Apache Ant, Derby, JBoss, NanoXML and Math). The results show that neither of the two techniques completely dominates the other, but they can potentially be complementary. Therefore, we next propose a novel approach that maximizes both code coverage and diversity among the selected test cases using NSGA-II multi- objective optimization, and the results show a significant improvement in fault detection rate. Specifically, sometimes this novel approach detects up to 16\%(Ant), 10\%(JBoss), and 14\% (Math) more faults compared to either of coverage or diversity-based approaches, when the testing budget is less than 20\% of the entire test suite execution cost.

We give an $O(n\log ^3 n)$-time linear-space algorithm that, given a plane 3-tree $G$ with $n$ vertices and a set $S$ of $n$ points in the plane, determines whether $G$ has a point-set embedding on $S$ (i.e., a planar straight-line drawing of $G$ where each vertex is mapped to a distinct point of $S$), improving the $O(n^{4/3+\varepsilon})$-time $O(n^{4/3})$-space algorithm of Moosa and Rahman [Lecture Notes in Comput. Sci. 6842, Springer, New York, 2011, pp. 204--212]. Given an arbitrary plane graph $G$ and a point set $S$, Kaufmann and Wiese [J. Graph Algorithms Appl., 6 (2002), pp. 115--129] gave an algorithm to compute 2-bend point-set embeddings of $G$ on $S$. Later, Di Giacomo and Liotta [Lecture Notes in Comput. Sci. 5942, Springer, New York, 2010, pp. 35--46] showed how such a drawing can be computed using $O(W^3)$ area, where $W$ is the length of the longest edge of the bounding box of $S$. Their algorithm uses $O(W^3)$ area even when the input graphs are restricted to plane 3-trees. We introduce new techniques for computing $2$-bend point-set embeddings of plane 3-trees that take only $O(W^2)$ area. We also give approximation algorithms for point-set embeddings of plane $3$-trees. Our results on 2-bend point-set embeddings and approximate point-set embeddings hold for partial plane $3$-trees (e.g., series-parallel graphs and Halin graphs).