Generative AI (GenAI) tools are increasingly used for spreadsheet tasks, yet little is known about how blind users verify their outputs in accuracy-critical contexts. We conducted a study with 12 blind spreadsheet users to explore verification practices across tasks such as information extraction, formula generation, trend analysis, chart creation, and formatting. Participants never fully trusted outputs without verification and employed diverse strategies, including manual checks with screen reader and spreadsheet features, same AI-assisted verification, cross-AI tool validation, leveraging prior knowledge, and human assistance. These approaches were adapted based on task context, perceived risk, and users’ expertise. Errors were common, particularly in chart generation and formatting, some detected, others overlooked. While verification improved confidence, it was often effortful, time-consuming, or infeasible for visual tasks. We discuss how blind users utilize GenAI not only as a task performer but also as a verification aid and validator, highlighting design opportunities for more accessible and reliable spreadsheet use.

Combining conversational AI with refreshable tactile displays (RTDs) offers significant potential for creating accessible data visualization for people who are blind or have low vision (BLV). To support researchers and developers building accessible data visualizations with RTDs, we present a multimodal data interaction architecture along with an open-source reference implementation. Our system is the first to combine touch input with a conversational agent on an RTD, enabling deictic queries that fuse touch context with spoken language, such as "what is the trend between these points?" The architecture addresses key technical challenges, including touch sensing on RTDs, visual-to-tactile encoding, integrating touch context with conversational AI, and synchronizing multimodal output. Our contributions are twofold: (1) a technical architecture integrating RTD hardware, external touch sensing, and conversational AI to enable multimodal data interaction; and (2) an open-source reference implementation demonstrating its feasibility. This work provides a technical foundation to support future research in multimodal accessible data visualization.

Tactile graphics are widely used to present maps and statistical diagrams to blind and low vision (BLV) people, with accessibility guidelines recommending their use for graphics where spatial relationships are important. Their use is expected to grow with the advent of commodity refreshable tactile displays. However, in stark contrast to visual information graphics, we lack a clear understanding of the benefts that well-designed tactile information graphics offer over text descriptions for BLV people. To address this gap, we introduce a framework considering the three components of encoding, perception and cognition to examine the known benefts for visual information graphics and explore their applicability to tactile information graphics. This work establishes a preliminary theoretical foundation for the tactile-frst design of information graphics and identifes future research avenues.

Cerebral Visual Impairment (CVI) is the set to be the leading cause of vision impairment, yet remains underrepresented in assistive technology research. Unlike ocular conditions, CVI affects higher-order visual processing-impacting object recognition, facial perception, and attention in complex environments. This paper presents a co-design study with two adults with CVI investigating how smart glasses, i.e. head-mounted extended reality displays, can support understanding and interaction with the immediate environment. Guided by the Double Diamond design framework, we conducted a two-week diary study, two ideation workshops, and ten iterative development sessions using the Apple Vision Pro. Our findings demonstrate that smart glasses can meaningfully address key challenges in locating objects, reading text, recognising people, engaging in conversations, and managing sensory stress. With the rapid advancement of smart glasses and increasing recognition of CVI as a distinct form of vision impairment, this research addresses a timely and under-explored intersection of technology and need.

3D printing is a mainstream technology enabling the affordable production of 3D models that may enhance access and understanding of graphics for students who are blind or have low vision (BLV). However, the potential usefulness of a new technology does not guarantee its adoption. This paper presents a case study in the adoption of 3D printing as an accessible format for BLV education in Australia and New Zealand. Over the last six years, a community-driven research project engaged in awareness raising, created a community of practice and developed guidelines for the use of 3D printing in education. We evaluate the success of the project using an Implementation Science lens with the RE-AIM framework and identify the key factors for successful adoption. We hope this work will guide the adoption of 3D printing for BLV students and serve as an exemplar for the adoption of other assistive technologies.

3D printed models (3DPMs) are increasingly used to support the education of students who are blind or have low vision (BLV). As 3DPMs are more widely-adopted, educators are using more complex multi-part models. However, with this increased complexity comes additional challenges for their use, such as supporting audio labels of multiple parts as well as guiding the assembly and disassembly of the model. This work explores the co-design and evaluation of a system that supports the use of multi-part 3DPMs by BLV students. Working with BLV adults and children, as well as educators, an iPad application was developed to support interaction with an insect model, including speech interaction and support for assembly. Evaluation showed that the system was strongly enjoyed by students and educators were enthusiastic as they believed it would increase classroom engagement and inclusion, and its support for voice annotation could be used for assessment.

Productivity applications including word processors, spreadsheets, and presentation tools are crucial in work, education, and personal settings. Blind users typically access these tools via screen readers (SRs) and face significant accessibility and usability challenges. Recent advancements in Generative AI (GenAI) may address these challenges by enabling natural language interactions and contextual task understanding. However, there is limited understanding of SR users' needs and attitudes toward GenAI assistance in these applications. We surveyed 99 SR users to gain a holistic understanding of the challenges they face when using productivity applications, the impact of these challenges on their productivity and independence, and their initial perceptions of AI assistance. Driven by their enthusiasm, we conducted interviews with 16 SR users to explore their attitudes toward GenAI and its potential usefulness in productivity applications. Our findings highlight its need to support existing SR workflows and the importance of enabling customization and task verification.

3D-printed models are increasingly used to provide people who are blind or have low vision (BLV) with access to maps, educational materials, and museum exhibits. Recent research has explored interactive 3D-printed models (I3Ms) that integrate touch gestures, conversational dialogue, and haptic vibratory feedback to create more engaging interfaces. Prior research with sighted people has found that imbuing machines with human-like behaviours, i.e., embodying them, can make them appear more lifelike, increasing social perception and presence. Such embodiment can increase engagement and trust. This work presents the first exploration into the design of embodied I3Ms and their impact on BLV engagement and trust. In a controlled study with 12 BLV participants, we found that I3Ms using specific embodiment design factors, such as haptic vibratory and embodied personified voices, led to an increased sense of liveliness and embodiment, as well as engagement, but had mixed impact on trust.

Despite the recent surge of research efforts to make data visualizations accessible to people who are blind or have low vision (BLV), how to support BLV people's data analysis remains an important and challenging question. As refreshable tactile displays (RTDs) become cheaper and conversational agents continue to improve, their combination provides a promising approach to support BLV people's interactive data exploration and analysis. To understand how BLV people would use and react to a system combining an RTD with a conversational agent, we conducted a Wizard-of-Oz study with 11 BLV participants, where they interacted with line charts, bar charts, and isarithmic maps. Our analysis of participants' interactions led to the identification of nine distinct patterns. We also learned that the choice of modalities depended on the type of task and prior experience with tactile graphics, and that participants strongly preferred the combination of RTD and speech to a single modality. In addition, participants with more tactile experience described how tactile images facilitated a deeper engagement with the data and supported independent interpretation. Our findings will inform the design of interfaces for such interactive mixed-modality systems.

Over the past decade, considerable research has investigated Vision-Based Assistive Technologies (VBAT) to support people with vision impairments to understand and interact with their immediate environment using machine learning, computer vision, image enhancement, and/or augmented/virtual reality. However, this has almost totally overlooked a growing demographic: people with Cerebral Visual Impairment (CVI). Unlike ocular vision impairments, CVI arises from damage to the brain’s visual processing centres. Through a scoping review, this paper reveals a significant research gap in addressing the needs of this demographic. Three focus studies involving 7 participants with CVI explored the challenges, current strategies, and opportunities for VBAT. We also discussed the assistive technology needs of people with CVI compared with ocular low vision. Our findings highlight the opportunity for the Human-Computer Interaction and Assistive Technologies research community to explore and address this underrepresented domain, thereby enhancing the quality of life for people with CVI.

Spreadsheets are widely used for storing, manipulating, analyzing, and visualizing data. Features such as conditional formatting, formulas, sorting, and filtering play an important role when understanding and analyzing data in spreadsheets. They employ visual cues, but we have little understanding of the experiences of blind screen reader (SR) users with such features. We conducted a study with 12 blind SR users to gain insights into their challenges, workarounds, and strategies in understanding and extracting information from a spreadsheet consisting of multiple tables that incorporated data analysis features. We identified five factors that impact blind SR users’ experiences: cognitive overload, time-information trade-off, lack of awareness and expertise, inadequate system feedback, and delayed and absent SR responses. Drawn from these findings, we discuss design suggestions and future research agenda to improve SR users’ spreadsheet experiences.

3D printed models have been used to improve access to graphical information by people who are blind, offering benefits over conventional accessible graphics. Here we investigate an interactive 3D printed model (I3M) that combines a conversational interface with haptic vibration and touch to provide more natural and accessible experiences. Specifically, we co-designed a multimodal model of the Solar System with nine blind people and evaluated the prototype with another seven blind participants. We discuss our journey from a design perspective, focusing on touch, conversational and multimodal interactions. Based on our experience, we suggest design recommendations that consider blind users’ desire for independence and control, customisation, comfort and use of prior experience.

With their overwhelming reliance on visual arts and artefacts, art galleries and museums are often considered unapproachable spaces for people who are blind or have low vision (BLV). We present the results of an ongoing collaboration with an Australian regional gallery in their efforts to improve access by BLV people to their permanent collection and temporary exhibitions. We describe the approach taken to develop interpretive technology-mediated experiences for BLV visitors for their 2021 and 2022 flagship exhibitions, along with evaluation from the perspectives of both BLV visitors and the gallery staff. Outcomes include: broader awareness within the gallery for inclusive design practice and public engagement; better understandings of the needs of BLV visitors, in particular relating to confidence building and technology integration; understanding of gallery constraints and challenges; and a framework for the development of future inclusive gallery experiences.

Over the last decade there has been considerable research into how artificial intelligence (AI), specifically computer vision, can assist people who are blind or have low-vision (BLV) to understand their environment. However, there has been almost no research into whether the tasks (object detection, image captioning, text recognition etc.) and devices (smartphones, smart-glasses etc.) investigated by researchers align with the needs and preferences of BLV people. We identified 646 studies published in the last two and a half years that have investigated such assistive AI techniques. We analysed these papers to determine the task, device and participation by BLV individuals. We then interviewed 24 BLV people and asked for their top five AI-based applications and to rank the applications found in the literature. We found only a weak positive correlation between BLV participants’ perceived importance of tasks and researchers’ focus and that participants prefer conversational agent interface and head-mounted devices.

Visual icons provide immediate recognition of features on print maps but do not translate well for touch reading by people who are blind or have low vision due to the low fidelity of tactile perception. We explored 3D printed icons as an equivalent to visual icons for tactile maps addressing these problems. We designed over 200 tactile icons (TactIcons) for street and park maps. These were touch tested by blind and sighted people, resulting in a corpus of 33 icons that can be recognised instantly and a further 34 icons that are easily learned. Importantly, this work has informed the creation of detailed guidelines for the design of TactIcons and a practical methodology for touch testing new TactIcons. It is hoped that this work will contribute to the creation of more inclusive, user-friendly tactile maps for people who are blind or have low vision.

Independent travel and navigation in new environments, in particular multi-storey buildings, is a major challenge for people who are blind or have low vision (BLV). Using tactile maps as part of orientation and mobility (O&M) training, BLV people can build a cognitive map of an environment before visiting. Tactile maps of multi-level environments, however, have received little attention. We investigated the usefulness of 3D printed models of buildings, through a user study with nine BLV adults. Three designs were evaluated: flat, overlapped-sliding and overlapped-rotating. All three designs were reported to be useful, usable, engaging and allowed participants to build a cognitive map of the building. There was a strong user preference for the overlapped presentations, which were reported to be more effective in supporting cross-floor spatial knowledge. This exploration of the design space of 3D building plans demonstrates their value and we hope will encourage their provision in O&M training.

We investigate reading strategies for node-link diagrams that wrap around the boundaries in a flattened torus topology by examining eye tracking data recorded in a previous controlled study. Prior work showed that torus drawing affords greater flexibility in clutter reduction than traditional node-link representations, but impedes link-and-path exploration tasks, while repeating tiles around boundaries aids comprehension. However, it remains unclear what strategies users apply in different wrapping settings. This is important for design implications for future work on more effective wrapped visualizations for network applications, and cyclic data that could benefit from wrapping. We perform visual-exploratory data analysis of gaze data, and conduct statistical tests derived from the patterns identified. Results show distinguishable gaze behaviors, with more visual glances and transitions between areas of interest in the non-replicated layout. Full-context has more successful visual searches than partial-context, but the gaze allocation indicates that the layout could be more space-efficient.

People who are blind rely on touch and hearing to understand the world around them, however it is extremely difficult to understand movement through these modes. The advent of refreshable tactile displays (RTDs) offers the potential for blind people to access tactile animations for the very first time. A survey of touch readers and vision accessibility experts revealed a high level of enthusiasm for tactile animations, particularly those relating to education, mapping and concept development. Based on these suggestions, a range of tactile animations were developed and four were presented to 12 touch readers. The RTD held advantages over traditional tactile graphics for conveying movement, depth and height, however there were trade-offs in terms of resolution and textural properties. This work offers a first glimpse into how refreshable tactile displays can best be utilised to convey animated graphics for people who are blind.

There are many methods for projecting spherical maps onto the plane. Interactive versions of these projections allow the user to centre the region of interest. However, the effects of such interaction have not previously been evaluated. In a study with 120 participants we find interaction provides significantly more accurate area, direction and distance estimation in such projections. The surface of 3D sphere and torus topologies provides a continuous surface for uninterrupted network layout. But how best to project spherical network layouts to 2D screens has not been studied, nor have such spherical network projections been compared to torus projections. Using the most successful interactive sphere projections from our first study, we compare spherical, standard and toroidal layouts of networks for cluster and path following tasks with 96 participants, finding benefits for both spherical and toroidal layouts over standard network layouts in terms of accuracy for cluster understanding tasks.

The ability to cross the street at intersections is an essential skill, often taught to people who are blind or have low vision (BLV) with the aid of tactile maps and kits or toys. However, each of the existing mapping tools has shortcomings. We investigated whether co-designed 3D printed components can offer benefits. Guided by consultation with 11 Orientation and Mobility (O&M) professionals, we co-designed a series of 3D printed kits that they then used in their practice with BLV children who showed high levels of engagement and learning. The 3D materials were found to demonstrate the key concepts for street crossings in a portable, engaging and professional manner. They will be released for free download, enabling O&M professionals to access or modify the materials as required. We hope that use of our co-designed 3D printed tools will contribute to the safety, independence and inclusion of BLV people.

Data visualisations are increasingly used online to engage readers and enable independent analysis of the data underlying news stories. However, access to such infographics is problematic for readers who are blind or have low vision (BLV). Equitable access to information is a basic human right and essential for independence and inclusion. We introduce infosonics, the audio equivalent of infographics, as a new style of interactive sonification that uses a spoken introduction and annotation, non-speech audio and sound design elements to present data in an understandable and engaging way. A controlled user evaluation with 18 BLV adults found a COVID-19 infosonic enabled a clearer mental image than a traditional sonification. Further, infosonics prove complementary to text descriptions and facilitate independent understanding of the data. Based on our findings, we provide preliminary suggestions for infosonics design, which we hope will enable BLV people to gain equitable access to online news and information.

User trust plays a key role in determining whether autonomous computer applications are relied upon. It will play a key role in the acceptance of emerging AI applications such as optimisation. Two important factors known to affect trust are system transparency, i.e., how well the user understands how the system works, and system performance. However, in the case of optimisation, it is difficult for the end-user to understand the underlying algorithms or to judge the quality of the solution. Through two controlled user studies, we explore whether the user is better able to calibrate their trust in the system when: (a) They are provided feedback on the system operation in the form of visualisation of intermediate solutions and their quality; (b) They can interactively explore the solution space by modifying the solution returned by the system. We found that showing intermediate solutions can lead to over-trust, while interactive exploration leads to more accurately calibrated trust.

In this paper, we report on a study of visual representations for cyclical data and the effect of interactively wrapping a bar chart 'around its boundaries'. Compared to linear bar chart, polar (or radial) visualisations have the advantage that cyclical data can be presented continuously without mentally bridging the visual 'cut' across the left-and-right boundaries. To investigate this hypothesis and to assess the effect the cut has on analysis performance, this paper presents results from a crowdsourced, controlled experiment with 72 participants comparing new continuous panning technique to linear bar charts (interactive wrapping). Our results show that bar charts with interactive wrapping lead to less errors compared to standard bar charts or polar charts. Inspired by these results, we generalise the concept of interactive wrapping to other visualisations for cyclical or relational data. We describe a design space based on the concept of one-dimensional wrapping and two-dimensional wrapping, linked to two common 3D topologies; cylinder and torus that can be used to metaphorically explain one- and two-dimensional wrapping. This design space suggests that interactive wrapping is widely applicable to many different data types.

This paper presents a systematic literature review of 292 publications from 97 unique venues on touch-based graphics for people who are blind or have low vision, from 2010 to mid-2020. It is the first review of its kind on touch-based accessible graphics. It is timely because it allows us to assess the impact of new technologies such as commodity 3D printing and low-cost electronics on the production and presentation of accessible graphics. As expected our review shows an increase in publications from 2014 that we can attribute to these developments. It also reveals the need to: broaden application areas, especially to the workplace; broaden end-user participation throughout the full design process; and conduct more in situ evaluation. This work is linked to an online living resource to be shared with the wider community.

We explore network visualisation on a two-dimensional torus topology that continuously wraps when the viewport is panned. That is, links may be “wrapped” across the boundary, allowing additional spreading of node positions to reduce visual clutter. Recent work has investigated such pannable wrapped visualisations, finding them not worse than unwrapped drawings for small networks for path-following tasks. However, they did not evaluate larger networks nor did they consider whether torus-based layout might also better display high-level network structure like clusters. We offer two algorithms for improving toroidal layout that is completely autonomous and automatic panning of the viewport to minimiswe wrapping links. The resulting layouts afford fewer crossings, less stress, and greater cluster separation. In a study of 32 participants comparing performance in cluster understanding tasks, we find that toroidal visualisation offers significant benefits over standard unwrapped visualisation in terms of improvement in error by 62.7% and time by 32.3%.

The HCI community has a rich history of finding new ways to engage people with data beyond the screen. With our work, we aim to expand the scope of how interaction design can engage people, arguing that “eating data” has the potential to allow people to experience “data as delight”. With reference to prior work and our design research findings, we discuss the advantages and the challenges of this approach to integrating data and food. We then identify four themes to guide the design of engagements with data through food: food form, food commensality, food ephemerality, and emotional response to food. Within these design themes, we articulate twelve insights for interaction designers to use when working on serving data as delight.

Efficient optimisation algorithms have become important tools for finding high-quality solutions to hard, real-world problems such as production scheduling, timetabling, or vehicle routing. These algorithms are typically "black boxes" that work on mathematical models of the problem to solve. However, many problems are difficult to fully specify, and require a "human in the loop" who collaborates with the algorithm by refining the model and guiding the search to produce acceptable solutions. Recently, the Problem-Solving Loop was introduced as a high-level model of such interactive optimisation. Here, we present and evaluate nine recommendations for the design of interactive visualisation tools supporting the Problem-Solving Loop. They range from the choice of visual representation for solutions and constraints to the use of a solution gallery to support exploration of alternate solutions. We first examined the applicability of the recommendations by investigating how well they had been supported in previous interactive optimisation tools. We then evaluated the recommendations in the context of the vehicle routing problem with time windows (VRPTW). To do so we built a sophisticated interactive visual system for solving VRPTW that was informed by the recommendations. Ten participants then used this system to solve a variety of routing problems. We report on participant comments and interaction patterns with the tool. These showed the tool was regarded as highly usable and the results generally supported the usefulness of the underlying recommendations.

data has no natural scale and so interactive data visualizations must provide techniques to allow the user to choose their viewpoint and scale. Such techniques are well established in desktop visualization tools. The two most common techniques are zoom+pan and overview+detail. However, how best to enable the analyst to navigate and view abstract data at different levels of scale in immersive environments has not previously been studied. We report the findings of the first systematic study of immersive navigation techniques for 3D scatterplots. We tested four conditions that represent our best attempt to adapt standard 2D navigation techniques to data visualization in an immersive environment while still providing standard immersive navigation techniques through physical movement and teleportation. We compared room-sized visualization versus a zooming interface, each with and without an overview. We find significant differences in participants' response times and accuracy for a number of standard visual analysis tasks. Both zoom and overview provide benefits over standard locomotion support alone (i.e., physical movement and pointer teleportation). However, which variation is superior, depends on the task. We obtain a more nuanced understanding of the results by analyzing them in terms of a time-cost model for the different components of navigation: way-finding, travel, number of travel steps, and context switching.

We introduce Tilt Map, a novel interaction technique for intuitively transitioning between 2D and 3D map visualisations in immersive environments. Our focus is visualising data associated with areal features on maps, for example, population density by state. Tilt Map transitions from 2D choropleth maps to 3D prism maps to 2D bar charts to overcome the limitations of each. Our article includes two user studies. The first study compares subjects' task performance interpreting population density data using 2D choropleth maps and 3D prism maps in virtual reality (VR). We observed greater task accuracy with prism maps, but faster response times with choropleth maps. The complementarity of these views inspired our hybrid Tilt Map design. Our second study compares Tilt Map to: a side-by-side arrangement of the various views; and interactive toggling between views. The results indicate benefits for Tilt Map in user preference; and accuracy (versus side-by-side) and time (versus toggle).

Node-link diagrams are widely used to visualise networks. However, even the best network layout algorithms ultimately result in 'hairball' visualisations when the graph reaches a certain degree of complexity, requiring simplification through aggregation or interaction (such as filtering) to remain usable. Until now, there has been little data to indicate at what level of complexity node-link diagrams become ineffective or how visual complexity affects cognitive load. To this end, we conducted a controlled study to understand workload limits for a task that requires a detailed understanding of the network topology-finding the shortest path between two nodes. We tested performance on graphs with 25 to 175 nodes with varying density. We collected performance measures (accuracy and response time), subjective feedback, and physiological measures (EEG, pupil dilation, and heart rate variability). To the best of our knowledge this is the first network visualisation study to include physiological measures. Our results show that people have significant difficulty finding the shortest path in high density node-link diagrams with more than 50 nodes and even low density graphs with more than 100 nodes. From our collected EEG data we observe functional differences in brain activity between hard and easy tasks. We found that cognitive load increased up to certain level of difficulty after which it decreased, likely because participants had given up. We also explored the effects of global network layout features such as size or number of crossings, and features of the shortest path such as length or straightness on task difficulty. We found that global features generally had a greater impact than those of the shortest path.

A critical component of the worldwide response to the novel coronavirus COVID-19 pandemic has been providing the general public with information about the virus and the health measures designed to slow its spread. Much of this information has been presented as visual graphics. Have people who are blind or have low vision (BLV) been able to gain access to this information through nonvisual media and, if so, how? We investigate this issue using Australia as a case study.

We present an autoethnographic study of an independent blind traveller, Kate. It recounts her preparation for a 28-day cruise and then her experience onboard the ship. Her planning notes, field notes and travel diary were analysed in terms of five main themes: information access, orientation and mobility, tools and technology, cultural and societal issues, and person-centred issues. This analysis provides a deeply personal account of the barriers–in particular information access, orientation and mobility and staff attitudes–that she faced, as well as the skills and tools that she used to overcome these. A particular focus is Kate’s use of technologies to access visual information and the provision of accessible maps and models before the trip to help her build a cognitive map of the ship’s layout.

Visualisations are commonly used to understand social, biological and other kinds of networks. Currently we do not know how to effectively present network data to people who are blind or have low-vision (BLV). We ran a controlled study with 8 BLV participants comparing four tactile representations: organic node-link diagram, grid node-link diagram, adjacency matrix and braille list. We found that the node-link representations were preferred and more effective for path following and cluster identification while the matrix and list were better for adjacency tasks. This is broadly in line with findings for the corresponding visual representations.

We investigate visualisations of networks on a 2-dimensional torus topology, like an opened-up and flattened doughnut. That is, the network is drawn on a rectangular area while "wrapping" specific links around the border. Previous work on torus drawings of networks has been mostly theoretical, limited to certain classes of networks, and not evaluated by human readability studies. We offer a simple interactive layout approach applicable to general graphs. We use this to find layouts affording better aesthetics in terms of conventional measures like more equal edge length and fewer crossings. In two controlled user studies we find that torus layout with either additional context or interactive panning provided significant performance improvement (in terms of error and time) over torus layout without either of these improvements, to the point that it is comparable to standard non-torus layout.

While developments in 3D printing have opened up opportunities for improved access to graphical information for people who are blind or have low vision (BLV), they can provide only limited detailed and contextual information. Interactive 3D printed models (I3Ms) that provide audio labels and/or a conversational agent interface potentially overcome this limitation. We conducted a Wizard-of-Oz exploratory study to uncover the multi-modal interaction techniques that BLV people would like to use when exploring I3Ms, and investigated their attitudes towards different levels of model agency. These findings informed the creation of an I3M prototype of the solar system. A second user study with this model revealed a hierarchy of interaction, with BLV users preferring tactile exploration, followed by touch gestures to trigger audio labels, and then natural language to fill in knowledge gaps and confirm understanding.

Immersive analytics turns the very space surrounding the user into a canvas for data analysis, supporting human cognitive abilities in myriad ways. We present the results of a design study, contextual inquiry, and longitudinal evaluation involving professional economists using a Virtual Reality (VR) system for multidimensional visualization to explore actual economic data. Results from our preregistered evaluation highlight the varied use of space depending on context (exploration vs. presentation), the organization of space to support work, and the impact of immersion on navigation and orientation in the 3D analysis space.

This article reviews two decades of research in topics in Information Visualisation emerging from the Data Visualisation and Immersive Analytics Lab at Monash University Australia (Monash IA Lab). The lab has been influential with contributions in algorithms, interaction techniques and experimental results in Network Visualisation, Interactive Optimisation and Geographic and Cartographic visualisation. It has also been a leader in the emerging topic of Immersive Analytics, which explores natural interactions and immersive display technologies in support of data analytics. We reflect on advances in these areas but also sketch our vision for future research and developments in data visualisation more broadly.

Providing people who are blind or have low vision with accessible versions of artworks is important not just for equity, but also for inclusion, greater engagement with the community at large, and raising awareness about these issues. In 2018, a value-sensitive design methodology was used with the Bendigo Art Gallery and key stakeholders to develop a model that provides three different ways of accessing the gallery, depending upon visual acuity and mobility: virtual tours, self-guided tours and guided tours. As a pilot implementation of the model, we developed different tactile representations of key artworks using tactile graphics, laser-cut layered graphics, 3D printed models, soundscapes, role plays, and a website featuring information and representations requested by workshop participants. To highlight the work, this paper will present two of the key works in more detail to highlight different representations that should be considered when presenting accessible artworks.

Access to information is a fundamental problem for people with vision impairment (PVI). Textual information are considerably more accessible with the use of screen readers that work on desktop and mobile devices. However, access to graphical information is still a challenging problem. There are different technologies to present graphics to PVI, but almost all of them suffer from practicality and portability. This paper describes the GraVVITAS (Graphics Viewer using Vibration Interactive Touch and Speech) framework which aims to be a complementary system for other assistive technologies; a solution that can be carried in one's pocket.

The difficulty and consequent fear of travel is one of the most disabling consequences of blindness and severe vision impairment, affecting confidence and quality of life. Traditional tactile graphics are vital in the Orientation and Mobility training process, however 3D printing may have the capacity to enable production of more meaningful and inclusive maps. This study explored the use of 3D printed maps on site at a public event to examine their suitability and to identify guidelines for the design of future 3D maps. An iterative design process was used in the production of the 3D maps, with feedback from visitors who are blind or have low vision informing the recommendations for their design and use. For example, it was found that many representational 3D icons could be recognised by touch without the need for a key and that such a map helped form mental models of the event space. Complex maps, however, require time to explore and should be made available before an event or at the entrance in a comfortable position. The maps were found to support the orientation and mobility process, and importantly to also promote a positive message about inclusion and accessibility.

While there is widespread recognition of the need to provide people with vision impairments (PVI) equitable access to cultural institutions such as art galleries, this is not easy. We present the results of a collaboration with a regional art gallery who wished to open their collection to PVIs in the local community. We describe a novel model that provides three different ways of accessing the gallery, depending upon visual acuity and mobility: virtual tours, self-guided tours and guided tours. As far as possible the model supports autonomous exploration by PVIs. It was informed by a value sensitive design exploration of the values and value conflicts of the primary stakeholders.

With the massive growth of online learning, there has been a decrease in students' face-to-face interactions, leading to rising feelings of isolation. This in turn contributes to several issues such as motivation loss, increased course attrition rates and poor learning experiences. Strong Online Learning Communities (OLCs) have been suggested as a means to help improve the situation, however the formation of OLCs is strongly influenced by learners' individual characteristics and their preferences regarding how and with whom they would want to form study groups. Taking students as its focus, this research attempts to develop a learning partner recommender system (LPRS) to facilitate finding compatible study peers in order to promote informal learning communities among students. From a synthesis of related literature and using data from a study of the student' preferences, a collection of learners' individual characteristics has been identified as a set of matching criteria in our LPRS model. A proof of concept based on the conceptual model has been developed and evaluated with a small group of target users. Results of the investigation showed positive feedback from participants and good prospects of the recommender system.

We introduce IATK, the Immersive Analytics Toolkit, a software package for Unity that allows interactive authoring and exploration of data visualisation in immersive environments. The design of IATK was informed by interdisciplinary expert-collaborations as well as visual analytics applications and iterative refinement over several years. IATK allows for easy assembly of visualisations through a grammar of graphics that a user can configure in a GUI-in addition to a dedicated visualisation API that supports the creation of novel immersive visualisation designs and interactions. IATK is designed with scalability in mind, allowing visualisation and fluid responsive interactions in the order of several million points at a usable frame rate. This paper outlines our design requirements, IATK's framework design and technical features, its user interface, as well as application examples.

Immersive virtual- and augmented-reality headsets can overlay a flat image against any surface or hang virtual objects in the space around the user. The technology is rapidly improving and may, in the long term, replace traditional flat panel displays in many situations. When displays are no longer intrinsically flat, how should we use the space around the user for abstract data visualisation? In this paper, we ask this question with respect to origin-destination flow data in a global geographic context. We report on the findings of three studies exploring different spatial encodings for flow maps. The first experiment focuses on different 2D and 3D encodings for flows on flat maps. We find that participants are significantly more accurate with raised flow paths whose height is proportional to flow distance but fastest with traditional straight line 2D flows. In our second and third experiment we compared flat maps, 3D globes and a novel interactive design we call MapsLink, involving a pair of linked flat maps. We find that participants took significantly more time with MapsLink than other flow maps while the 3D globe with raised flows was the fastest, most accurate, and most preferred method. Our work suggests that careful use of the third spatial dimension can resolve visual clutter in complex flow maps.

We evaluate the relative merits of three techniques for visualising multivariate data: parallel coordinates; scatterplot matrix; and a side-by-side, coordinated combination of these views. In particular, we report on: (1) the most effective visual encoding of multivariate data for each of the six common tasks considered; (2) common strategies that our participants used when the two views were combined based on eye-tracking data analysis; (3) the finding that these views are perceptually complementary in the sense that they both show the same information, but with different and complementary support for different types of analysis. For the combined view, our studies show that there is a perceptually complementary effect in terms of significantly improved accuracy for certain tasks, but that there is a small cost in terms of slightly longer completion time than the faster of the two techniques alone. Eye-movement data shows that for many tasks participants were able to swiftly switch their strategies after trying both in the training phase.

Tactile maps are widely used in Orientation and Mobility (O&M) training for people with blindness and severe vision impairment. Commodity 3D printers now offer an alternative way to present accessible graphics, however it is unclear if 3D models offer advantages over tactile equivalents for 2D graphics such as maps. In a controlled study with 16 touch readers, we found that 3D models were preferred, enabled the use of more easily understood icons, facilitated better short term recall and allowed relative height of map elements to be more easily understood. Analysis of hand movements revealed the use of novel strategies for systematic scanning of the 3D model and gaining an overview of the map. Finally, we explored how 3D printed maps can be augmented with interactive audio labels, replacing less practical braille labels. Our findings suggest that 3D printed maps do indeed offer advantages for O&M training.

Abstract This paper explores different ways to render world‐wide geographic maps in virtual reality (VR). We compare: (a) a 3D exocentric globe, where the user's viewpoint is outside the globe; (b) a flat map (rendered to a plane in VR); (c) an egocentric 3D globe, with the viewpoint inside the globe; and (d) a curved map, created by projecting the map onto a section of a sphere which curves around the user. In all four visualisations the geographic centre can be smoothly adjusted with a standard handheld VR controller and the user, through a head‐tracked headset, can physically move around the visualisation. For distance comparison exocentric globe is more accurate than egocentric globe and flat map. For area comparison more time is required with exocentric and egocentric globes than with flat and curved maps. For direction estimation, the exocentric globe is more accurate and faster than the other visual presentations. Our study participants had a weak preference for the exocentric globe. Generally the curved map had benefits over the flat map. In almost all cases the egocentric globe was found to be the least effective visualisation. Overall, our results provide support for the use of exocentric globes for geographic visualisation in mixed‐reality.

The fields of operations research and computer science have long sought to find automatic solver techniques that can find high-quality solutions to difficult real-world optimisation problems. The traditional workflow is to exactly model the problem and then enter this model into a general-purpose "black-box" solver. In practice, however, many problems cannot be solved completely automatically, but require a "human-in-the-loop" to iteratively refine the model and give hints to the solver. In this paper, we explore the parallels between this interactive optimisation workflow and the visual analytics sense-making loop. We assert that interactive optimisation is essentially a visual analytics task and propose a problem-solving loop analogous to the sense-making loop. We explore these ideas through an in-depth analysis of a use-case in prostate brachytherapy, an application where interactive optimisation may be able to provide significant assistance to practitioners in creating prostate cancer treatment plans customised to each patient's tumour characteristics. However, current brachytherapy treatment planning is usually a careful, mostly manual process involving multiple professionals. We developed a prototype interactive optimisation tool for brachytherapy that goes beyond current practice in supporting focal therapy - targeting tumour cells directly rather than simply seeking coverage of the whole prostate gland. We conducted semi-structured interviews, in two stages, with seven radiation oncology professionals in order to establish whether they would prefer to use interactive optimisation for treatment planning and whether such a tool could improve their trust in the novel focal therapy approach and in machine generated solutions to the problem.

We propose Graph Thumbnails, small icon-like visualisations of the high-level structure of network data. Graph Thumbnails are designed to be legible in small multiples to support rapid browsing within large graph corpora. Compared to existing graph-visualisation techniques our representation has several advantages: (1) the visualisation can be computed in linear time; (2) it is canonical in the sense that isomorphic graphs will always have identical thumbnails; and (3) it provides precise information about the graph structure. We report the results of two user studies. The first study compares Graph Thumbnails to node-link and matrix views for identifying similar graphs. The second study investigates the comprehensibility of the different representations. We demonstrate the usefulness of this representation for summarising the evolution of protein-protein interaction networks across a range of species.

We explore the relative merits of matrix, node-link and combined side-by-side views for the visualisation of weighted networks with three controlled studies: (1) finding the most effective visual encoding for weighted edges in matrix representations; (2) comparing matrix, node-link and combined views for static weighted networks; and (3) comparing MatrixWave, Sankey and combined views of both for event-sequence data. Our studies underline that node-link and matrix views are suited to different analysis tasks. For the combined view, our studies show that there is a perceptually complementary effect in terms of improved accuracy for some tasks, but that there is a cost in terms of longer completion time than the faster of the two techniques alone. Eye-movement data shows that for many tasks participants strongly favour one of the two views, after trying both in the training phase.

Document engineering is all about building systems and tools that allow people to work with documents and document collections. A key aspect is the usefulness and usability of these tools. In this tutorial, we will look at the many different kinds of user studies and user evaluations that can be used to inform the design and improve utility and usability of document engineering applications. The tutorial will be based on actual studies and will also give participants a chance to explore how they might use these techniques in their research or system development.

Libraries are increasingly offering on-line digital access to their collections. However, traditional search-based interfaces are restrictive and do not encourage the user to explore the collection in the same way that a physical collection does. We present the Mitchell WordCloud, a novel on-line interface to the David Scott Mitchell collection of the State Library of New South Wales. Based on interface design principles for explorative search, it presents the user with a word cloud derived from the collection and a list of titles. As the user drags words from the word cloud to tell the system what they like or dislike the title list is reordered. The surrounding interface elements -- image bar, time line and Dewey bar -- provide complementary insights into the collection. The traditional vector space model for measuring text similarity was extended to take account of user dislikes and to order words in the word cloud. User studies confirmed that the Mitchell WordCloud is easy to use and encourages exploration.

We are developing an application to automatically generate an accessible graphic from a floor plan image. Floor plans generally contain large regions with functionally different sub-areas. A problem faced by visually impaired users in exploring such accessible floor plans is understanding the boundaries of these sub-areas. We present an effective method to partition such open plan areas. Initially, we conducted a formative user study to understand how people partition open plan areas. Based on the findings of the study, we identified a general set of guidelines for partitioning open plans. These guidelines were used to generate a set of candidate lines for sub-areas. An obstacle avoiding shortest-path Voronoi diagram was used to determine boundaries for each sub-area. Candidate lines such as wall extensions were automatically generated to replace the identified boundaries. We selected the best replacement for each boundary by scoring candidate lines using a set of criteria such as line length. Finally the proposed method was tested on a standard floor plan corpus using three novel measures.

We introduce ImAxes immersive system for exploring multivariate data using fluid, modeless interaction. The basic interface element is an embodied data axis. The user can manipulate these axes like physical objects in the immersive environment and combine them into sophisticated visualisations. The type of visualisation that appears depends on the proximity and relative orientation of the axes with respect to one another, which we describe with a formal grammar. This straight-forward composability leads to a number of emergent visualisations and interactions, which we review, and then demonstrate with a detailed multivariate data analysis use case.

In this paper, we investigate Confluent Drawings (CD), a technique for bundling edges in node-link diagrams based on network connectivity. Edge-bundling techniques are designed to reduce edge clutter in node-link diagrams by coalescing lines into common paths or bundles. Unfortunately, traditional bundling techniques introduce ambiguity since edges are only bundled by spatial proximity, rather than network connectivity; following an edge from its source to its target can lead to the perception of incorrect connectivity if edges are not clearly separated within the bundles. Contrary, CDs bundle edges based on common sources or targets. Thus, a smooth path along a confluent bundle indicates precise connectivity. While CDs have been described in theory, practical investigation and application to real-world networks (i.e., networks beyond those with certain planarity restrictions) is currently lacking. Here, we provide the first algorithm for constructing CDs from arbitrary directed and undirected networks and present a simple layout method, embedded in a sand box environment providing techniques for interactive exploration. We then investigate patterns and artifacts in CDs, which we compare to other common edge-bundling techniques. Finally, we present the first user study that compares edge-compression techniques, including CD, power graphs, metro-style, and common edge bundling. We found that users without particular expertise in visualization or network analysis are able to read small CDs without difficulty. Compared to existing bundling techniques, CDs are more likely to allow people to correctly perceive connectivity.

High-quality immersive display technologies are becoming mainstream with the release of head-mounted displays (HMDs) such as the Oculus Rift. These devices potentially represent an affordable alternative to the more traditional, centralised CAVE-style immersive environments. One driver for the development of CAVE-style immersive environments has been collaborative sense-making. Despite this, there has been little research on the effectiveness of collaborative visualisation in CAVE-style facilities, especially with respect to abstract data visualisation tasks. Indeed, very few studies have focused on the use of these displays to explore and analyse abstract data such as networks and there have been no formal user studies investigating collaborative visualisation of abstract data in immersive environments. In this paper we present the results of the first such study. It explores the relative merits of HMD and CAVE-style immersive environments for collaborative analysis of network connectivity, a common and important task involving abstract data. We find significant differences between the two conditions in task completion time and the physical movements of the participants within the space: participants using the HMD were faster while the CAVE2 condition introduced an asymmetry in movement between collaborators. Otherwise, affordances for collaborative data analysis offered by the low-cost HMD condition were not found to be different for accuracy and communication with the CAVE2. These results are notable, given that the latest HMDs will soon be accessible (in terms of cost and potentially ubiquity) to a massive audience.

Showing flows of people and resources between multiple geographic locations is a challenging visualisation problem. We conducted two quantitative user studies to evaluate different visual representations for such dense many-to-many flows. In our first study we compared a bundled node-link flow map representation and OD Maps [37] with a new visualisation we call MapTrix. Like OD Maps, MapTrix overcomes the clutter associated with a traditional flow map while providing geographic embedding that is missing in standard OD matrix representations. We found that OD Maps and MapTrix had similar performance while bundled node-link flow map representations did not scale at all well. Our second study compared participant performance with OD Maps and MapTrix on larger data sets. Again performance was remarkably similar.

Over the last 50 years a wide variety of automatic network layout algorithms have been developed. Some are fast heuristic techniques suitable for networks with hundreds of thousands of nodes while others are multi-stage frameworks for higher-quality layout of smaller networks. However, despite decades of research currently no algorithm produces layout of comparable quality to that of a human. We give a new "human-centred" methodology for automatic network layout algorithm design that is intended to overcome this deficiency. User studies are first used to identify the aesthetic criteria algorithms should encode, then an algorithm is developed that is informed by these criteria and finally, a follow-up study evaluates the algorithm output. We have used this new methodology to develop an automatic orthogonal network layout method, HOLA, that achieves measurably better (by user study) layout than the best available orthogonal layout algorithm and which produces layouts of comparable quality to those produced by hand.

Prior research into network layout has focused on fast heuristic techniques for layout of large networks, or complex multi-stage pipelines for higher quality layout of small graphs. Improvements to these pipeline techniques, especially for orthogonal-style layout, are difficult and practical results have been slight in recent years. Yet, as discussed in this paper, there remain significant issues in the quality of the layouts produced by these techniques, even for quite small networks. This is especially true when layout with additional grouping constraints is required. The first contribution of this paper is to investigate an ultra-compact, grid-like network layout aesthetic that is motivated by the grid arrangements that are used almost universally by designers in typographical layout. Since the time when these heuristic and pipeline-based graph-layout methods were conceived, generic technologies (MIP, CP and SAT) for solving combinatorial and mixed-integer optimization problems have improved massively. The second contribution of this paper is to reassess whether these techniques can be used for high-quality layout of small graphs. While they are fast enough for graphs of up to 50 nodes we found these methods do not scale up. Our third contribution is a large-neighborhood search meta-heuristic approach that is scalable to larger networks.

We present a new approach for providing mathematical and statistical graphics to people who are blind or have severe vision impairment and describe the implementation and initial evaluation of an accessible graphing calculator, GraCALC. GraCALC automatically creates a graphic from a specification of the function or a tabular data using a web based service. The graphic is then presented on a touch device, and a mixture of speech, non-speech audio and optional tactile feedback are provided to allow the users explore the screen. An overview containing a sonification of the graphic and a description similar to that created by a human transcriber is also automatically generated so as to help the user in their initial navigation.

Paper is still the dominant medium in academic reading. One reason is the ease of navigation within a paper document. We therefore investigate how to provide a more paper-like navigation within an academic document when read digitally. We present the results of a user study in which we compare the standard single-view hyperlink navigation with a split-view navigation. The split-view offers the reader a primary reading view of the document as well as a contextual view next to it. When a hyperlink is activated in the reading view the contextual view shows the referenced element. While we found no difference between user performance, the split-view was preferred by almost all users to the standard single-view navigation model.

We present a new model for presenting graphics in eBooks to blind readers. It is based on the GraViewer app which allows an accessible graphic embedded in an iBook to be explored on an iPad using speech and non-speech audio feedback. We also introduce a web-based tool, GraAuthor, for creating such accessible graphics and describe the workflow for including these in an iBook. Unlike previous approaches our model provides an integrated digital presentation of both text and graphics and allows the general public to create accessible graphics.

Document content is increasingly customised to a particular audience. Such customised documents are typically built by combining content from selected logical content modules and then editing this to create the custom document. A major difficulty is how to efficiently update these derived documents when the source documents are changed. Here we describe a web-based visual editing tool for both creating and semi-automatically updating derived documents from modules in a source library.

We draw from the domains of Visual Analytics and Augmented Reality to support a new form of in-situ interactive visual analysis. We present a Situated Analytics model, a novel interaction, and a visualization concept for reasoning support. Situated Analytics has four primary elements: situated information, abstract information, augmented reality interaction, and analytical interaction.

Better access to on-line information graphics is a pressing need for people who are blind or have severe vision impairment. We present a new model for accessible presentation of on-line information graphics and demonstrate its use for presenting floor plans. While floor plans are increasingly provided on-line, people who are blind are at best provided with only a high-level textual description. This makes it difficult for them to understand the spatial arrangement of the objects on the floor plan. Our new approach provides users with significantly better access to such plans. The users can automatically generate an accessible version of a floor plan from an on-line floor plan image quickly and independently by using a web service. This generates a simplified graphic showing the rooms, walls, doors and windows in the original floor plan as well as a textual overview. The accessible floor plan is presented on an iPad using audio feedback. As the users touch graphic elements on the screen, the element they are touching is described by speech and non-speech audio in order to help them navigate the graphic.

Automatic layout of tables is useful in word processing applications and is required in online applications because of the need to tailor the layout to viewport width, choice of font, and dynamic content. However, if the table contains text, minimizing the height of the table for a given maximum width is a difficult combinatorial optimization problem because of the need to find the right choice of height/width configuration for each cell in the table. We investigate the modelling decisions involved in formulating this problem for use with standard combinatorial optimization techniques that are guaranteed to find the minimal-height table. To the best of our knowledge, we are the first to do so. We provide a detailed empirical evaluation of the resulting models using mixed integer programming and constraint programming with lazy clause generation.

Drawings of highly connected (dense) graphs can be very difficult to read. Power Graph Analysis offers an alternate way to draw a graph in which sets of nodes with common neighbours are shown grouped into modules. An edge connected to the module then implies a connection to each member of the module. Thus, the entire graph may be represented with much less clutter and without loss of detail. A recent experimental study has shown that such lossless compression of dense graphs makes it easier to follow paths. However, computing optimal power graphs is difficult. In this paper, we show that computing the optimal power-graph with only one module is NP-hard and therefore likely NP-hard in the general case. We give an ILP model for power graph computation and discuss why ILP and CP techniques are poorly suited to the problem. Instead, we are able to find optimal solutions much more quickly using a custom search method. We also show how to restrict this type of search to allow only limited back-tracking to provide a heuristic that has better speed and better results than previously known heuristics.

Researchers constantly read and annotate academic documents. While almost all documents are provided digitally, many are still printed and read on paper. We surveyed 162 academics in order to better understand their reading habits and preferences. We were particularly interested in understanding the barriers to digital reading and the features desired by academics for digital reading applications.

BACKGROUND: Biologists make frequent use of databases containing large and complex biological networks. One popular database is the Kyoto Encyclopedia of Genes and Genomes (KEGG) which uses its own graphical representation and manual layout for pathways. While some general drawing conventions exist for biological networks, arbitrary graphical representations are very common. Recently, a new standard has been established for displaying biological processes, the Systems Biology Graphical Notation (SBGN), which aims to unify the look of such maps. Ideally, online repositories such as KEGG would automatically provide networks in a variety of notations including SBGN. Unfortunately, this is non-trivial, since converting between notations may add, remove or otherwise alter map elements so that the existing layout cannot be simply reused. RESULTS: Here we describe a methodology for automatic translation of KEGG metabolic pathways into the SBGN format. We infer important properties of the KEGG layout and treat these as layout constraints that are maintained during the conversion to SBGN maps. CONCLUSIONS: This allows for the drawing and layout conventions of SBGN to be followed while creating maps that are still recognizably the original KEGG pathways. This article details the steps in this process and provides examples of the final result.

We explore the effectiveness of visualizing dense directed graphs by replacing individual edges with edges connected to 'modules'-or groups of nodes-such that the new edges imply aggregate connectivity. We only consider techniques that offer a lossless compression: that is, where the entire graph can still be read from the compressed version. The techniques considered are: a simple grouping of nodes with identical neighbor sets; Modular Decomposition which permits internal structure in modules and allows them to be nested; and Power Graph Analysis which further allows edges to cross module boundaries. These techniques all have the same goal--to compress the set of edges that need to be rendered to fully convey connectivity--but each successive relaxation of the module definition permits fewer edges to be drawn in the rendered graph. Each successive technique also, we hypothesize, requires a higher degree of mental effort to interpret. We test this hypothetical trade-off with two studies involving human participants. For Power Graph Analysis we propose a novel optimal technique based on constraint programming. This enables us to explore the parameter space for the technique more precisely than could be achieved with a heuristic. Although applicable to many domains, we are motivated by--and discuss in particular--the application to software dependency analysis.

Automatic layout of tables is required in online applications because of the need to tailor the layout to the viewport width, choice of font, and dynamic content. However, if the table contains text, minimizing the height of the table for a fixed maximum width is NP-hard. Thus, more efficient heuristic algorithms are required. We evaluate the HTML table layout recommendation and find that while it generally produces quite compact layout it is brittle and can lead to quite uncompact layout. We present an alternate heuristic algorithm. It uses a greedy strategy that starts from the widest reasonable layout and repeatedly chooses to narrow the column for which narrowing leads to the least increase in table height. The algorithm is simple, fast enough to be used in online applications, and gives significantly more compact layout than is obtained with HTML’s recommended table layout algorithm.

Guillotine-based page layout is a method for document layout commonly used by newspapers and magazines, where each region of the page either contains a single article, or is recursively split either vertically or horizontally. Suprisingly there appears to be little research into algorithms for automatic guillotine-based document layout. In this paper we give efficient algorithms to find optimal solutions to guillotine layout problems of two forms. Fixed-cut layout is where the structure of the guillotining is given and we only have to determine the best configuration for each individual article to give the optimal total configuration. Free layout is where we also have to search for the optimal structure. We give bottom-up and top-down dynamic programming algorithms to solve these problems, and propose a novel interaction model for documents on electronic media. Experiments show that our algorithms are effective for realistic layout problems.

Typesetting software is often faced with conflicting aesthetic goals. For example, choosing where to break lines in text might involve aiming to minimize hyphenation, variation in word spacing, and consecutive lines starting with the same word. Typically, automatic layout is modelled as an optimization problem in which the goal is to minimize a complex objective function that combines various penalty functions each of which corresponds to a particular bad feature. Determining how to combine these penalty functions is difficult and very time consuming, becoming harder each time we add another penalty. Here we present a machine-learning approach to do this, and test it in the context of line-breaking. Our approach repeatedly queries the expert typographer as to which one of a pair of layouts is better, and accordingly refines the estimate of how best to weight the penalties in a linear combination. It chooses layout pair queries by a heuristic to maximize the amount that can be learnt from them so as to reduce the number of combinations that must be considered by the typographer.

We investigate the cognitive impact of various layout features-symmetry, alignment, collinearity, axis alignment and orthogonality - on the recall of network diagrams (graphs). This provides insight into how people internalize these diagrams and what features should or shouldn't be utilised when designing static and interactive network-based visualisations. Participants were asked to study, remember, and draw a series of small network diagrams, each drawn to emphasise a particular visual feature. The visual features were based on existing theories of perception, and the task enabled visual processing at the visceral level only. Our results strongly support the importance of visual features such as symmetry, collinearity and orthogonality, while not showing any significant impact for node-alignment or parallel edges.

Automatic layout of tables is useful in word processing applications and is required in on-line applications because of the need to tailor the layout to the viewport width, choice of font and dynamic content. However, if the table contains text, minimizing the height of the table for a fixed maximum width is a difficult combinatorial optimization problem. We present three different approaches to finding the minimum height layout based on standard approaches for combinatorial optimization. All are guaranteed to find the optimal solution. The first is an A*-based approach that uses an admissible heuristic based on the area of the cell content. The second and third are constraint programming (CP) approaches using the same CP model. The second approach uses traditional CP search, while the third approach uses a hybrid CP/SAT approach, lazy clause generation, that uses learning to reduce the search required. We provide a detailed empirical evaluation of the three approaches and also compare them with two mixed integer programming (MIP) encodings due to Bilauca and Healy.

We introduce hi-trees, a new visual representation for hierarchical data in which, depending on the kind of parent node, the child relationship is represented using either containment or links. We give a drawing convention for hi-trees based on the standard layered drawing convention for rooted trees, then show how to extend standard bottom-up tree layout algorithms to draw hi-trees in this convention. We also explore a number of other more compact layout styles for layout of larger hi-trees and give algorithms for computing these. Finally, we describe two applications of hi-trees: argument mapping and business decision support.

We review the literature on automatic document formatting with an emphasis on recent work in the field. One common way to frame document formatting is as a constrained optimization problem where decision variables encode element placement, constraints enforce required geometric relationships, and the objective function measures layout quality. We present existing research using this framework, describing the kind of optimization problem being solved and the basic optimization techniques used to solve it. Our review focuses on the formatting of primarily textual documents, including both micro- and macro-typographic concerns. We also cover techniques for automatic table layout. Related problems such as widget and diagram layout, as well as temporal layout issues that arise in multimedia documents are outside the scope of this review.

The standard layout model used by web browsers is to lay text out in a vertical scroll using a single column. The horizontal-scroll layout model--in which text is laid out in columns whose height is set to that of the browser window and the viewer scrolls horizontally - seems well-suited to multi-column layout on electronic devices. We describe a study that examines how people read and, in particular, the strategies they use for scrolling with these two models when reading large textual documents on a standard computer monitor. We compare usability of the models and evaluate both user preferences and the effect of the model on performance. Also interesting is the description of the browser and its user interface which we used for the study.

BACKGROUND: Biological networks are widely used to represent processes in biological systems and to capture interactions and dependencies between biological entities. Their size and complexity is steadily increasing due to the ongoing growth of knowledge in the life sciences. To aid understanding of biological networks several algorithms for laying out and graphically representing networks and network analysis results have been developed. However, current algorithms are specialized to particular layout styles and therefore different algorithms are required for each kind of network and/or style of layout. This increases implementation effort and means that new algorithms must be developed for new layout styles. Furthermore, additional effort is necessary to compose different layout conventions in the same diagram. Also the user cannot usually customize the placement of nodes to tailor the layout to their particular need or task and there is little support for interactive network exploration. RESULTS: We present a novel algorithm to visualize different biological networks and network analysis results in meaningful ways depending on network types and analysis outcome. Our method is based on constrained graph layout and we demonstrate how it can handle the drawing conventions used in biological networks. CONCLUSION: The presented algorithm offers the ability to produce many of the fundamental popular drawing styles while allowing the exibility of constraints to further tailor these layouts.

We have implemented a Java application that automatically generates tactile bar and pie charts from data values given in a formatted text file. The tool is designed to semi-automate the construction of tactile versions of bar and pie charts in educational material. The tool provides a wide variety of layout styles. While the tool allows the user to fine tune the layout, the generated SVG diagram can also be modified in a standard diagram editor.

We present at a new approach to finding aesthetically pleasing page layouts. We do not aim to find an optimal layout, rather the aim is to find a layout which is not obviously wrong. We consider vertical scroll-like layout with floating figures referenced within the text where floats can have alternate sizes, may be optional, move from one side to the other and change their order. We also allow pagination. Our approach is to use a randomised local search algorithm to explore different configurations of floats, i.e. choice of floats and relative ordering. For a particular float configuration we use an efficient gradient projection-like continuous optimization algorithm. The resulting system is fast and provides an efficient warm start option to improve interactive support.

The web and digital media requires intelligent, adaptive documents whose appearance and content adapts to the viewing context and which support user interaction. While previous research has focussed on textual and multimedia content, this is also true for diagrammatic conte nt. We have designed and implemented an authoring tool which supports the construction of adaptive diagrams. Adaptive layout behaviour is specified by using constraint-based placement tools as well as by allowing the author to specify more radical layout changes using alternate layout configurations. As well as specifying alternate layouts, the author can specify alternate representations for an object, alternate styles and alternate textual content. The resulting space of different versions of the diagram is the cross product of these different alternatives. At display time the version is constructed dynamically, taking into account the author specified preference order on the alternatives, current viewing environment, and user interaction.

We investigate the usability of constraint-based alignment and distribution placement tools in diagram editors. Currently one-way constraints are used to provide alignment and distribution tools in many commercial editors. We believe the limitations of these constraints lead to serious usability issues, and thus suggest that such tools be implemented using multi-way constraints. We have conducted two usability studies, the first studies we are aware of that examine the relative usefulness of interactive graphical tools based on one-way and multi-way constraints. They provide strong evidence that multi-way constraint-based alignment and distribution tools are more usable than one-way constraint-based alignment and distribution tools.

A standard approach to large network visualization is to provide an overview of the network and a detailed view of a small component of the graph centred around a focal node. The user explores the network by changing the focal node in the detailed view or by changing the level of detail of a node or cluster. For scalability, fast force-based layout algorithms are used for the overview and the detailed view. However, using the same layout algorithm in both views is problematic since layout for the detailed view has different requirements to that in the overview. Here we present a model in which constrained graph layout algorithms are used for layout in the detailed view. This means the detailed view has high-quality layout including sophisticated edge routing and is customisable by the user who can add placement constraints on the layout. Scalability is still ensured since the slower layout techniques are only applied to the small subgraph shown in the detailed view. The main technical innovations are techniques to ensure that the overview and detailed view remain synchronized, and modifying constrained graph layout algorithms to support smooth, stable layout. The key innovation supporting stability are new dynamic graph layout algorithms that preserve the topology or structure of the network when the user changes the focus node or the level of detail by in situ semantic zooming. We have built a prototype tool and demonstrate its use in two application domains, UML class diagrams and biological networks.

Given possibly non-rectangular shapes, S1, ..., Sn, and some English text, T, we give methods based on approximating T by its area that determine for each Si whether T definitely fits in Si, definitely does not fit in Si, or probably fits in Si. These methods have complexity linear in the size of Si, assuming it is represented as a trapezoid list, but do not depend on the size of T. They require a linear time shape independent pre-processing of the text.

Multi-column layout with horizontal scrolling has a number of advantages over the standard model (single column with vertical scrolling) for on-line document layout. However, one difficulty with the multi-column model is the need for good automatic placement of floating figures. We identify reasonable aesthetic criteria for their placement, and then give a dynamic-programming-like algorithm for finding an optimal layout with respect to these criteria. We also investigate an A* based approach and give two variants differing in the choice of heuristic. We find that one of the A* based approaches is faster than the dynamic programming approach and, if a "window" of optimization is used, fast enough for moderately sized documents.

Automatic table layout is required in web applications. Unfortunately, this is NP-hard for reasonable layout requirements such as minimizing table height for a given width. One approach is to solve a continuous relaxation of the layout problem in which each cell must be large enough to contain the area of its content. The solution to this relaxed problem can then guide the solution to the original problem. We give a simple and efficient algorithm for solving this continuous relaxation for the case that cells do not span multiple columns or rows. The algorithm is not only interesting in its own right but also because it provides insight into the geometry of table layout.

In many text-processing applications, we would like shapes that expand (or shrink) in size to fit their textual content. We address how to efficiently compute the minimum size for such text shapes. A variant of this problem is to take a fixed shape and determine the maximal size font that will still allow the content to fit into it. Our approach is to model the problem as a constrained optimisation problem with a single variable that controls the geometry of the text shape. We use a variant of secant search to determine the minimum area for the shape, guided by the area of the text. We represent the shape by regions that are composed of trapezoids whose coordinates are a linear function of the unknown variable. This allows us to use a novel linear time algorithm (based on computing Minkowski difference) that takes a trapezoid list and text height and determines the region in which a line of text of that height and some minimum width can start and still remain inside the shape.

We describe a new method for visualization of directed graphs. The method combines constraint programming techniques with a high performance force-directed placement (FDP) algorithm. The resulting placements highlight hierarchy in directed graphs while retaining useful properties of FDP; such as emphasis of symmetries and preservation of proximity relations. Our algorithm automatically identifies those parts of the digraph that contain hierarchical information and draws them accordingly. Additionally, those parts that do not contain hierarchy are drawn at the same quality expected from a nonhierarchical, undirected layout algorithm. Our experiments show that this new approach is better able to convey the structure of large digraphs than the most widely used hierarchical graph-drawing method. An interesting application of our algorithm is directional multidimensional scaling (DMDS). DMDS deals with low-dimensional embedding of multivariate data where we want to emphasize the overall flow in the data (e.g., chronological progress) along one of the axes.

We extend the popular force-directed approach to network (or graph) layout to allow separation constraints, which enforce a minimum horizontal or vertical separation between selected pairs of nodes. This simple class of linear constraints is expressive enough to satisfy a wide variety of application-specific layout requirements, including: layout of directed graphs to better show flow; layout with non-overlapping node labels; and layout of graphs with grouped nodes (called clusters). In the stress majorization force-directed layout process, separation constraints can be treated as a quadratic programming problem. We give an incremental algorithm based on gradient projection for efficiently solving this problem. The algorithm is considerably faster than using generic constraint optimization techniques and is comparable in speed to unconstrained stress majorization. We demonstrate the utility of our technique with sample data from a number of practical applications including gene-activation networks, terrorist networks and visualization of high-dimensional data.

Tables are provided in virtually all document formatting systems and are one of the most powerful and useful design elements in current web document standards. Unfortunately, optimal layout of tables which contain text is NP-hard for reasonable layout requirements such as minimizing table height for a given width [1]. We present two new independently-applicable techniques for table layout. The first technique is to solve a continuous approximation to the original layout problem by using a constant-area approximation of the cell content combined with a minimum width and height for the cell. The second technique starts by setting each column to its narrowest possible width and then iteratively reduces the height of the table by judiciously widening its columns. This second technique uses the actual text and line-break rules rather than the constant-area approximation used by the first technique. We also investigate two hybrid approaches both of which use iterative column widening to improve the quality of an initial solution found using a different technique. In the first hybrid approach we use the continuous approximation technique to compute the initial column widths while in the second hybrid approach a modification of the HTML table layout algorithm is used to compute the initial widths. We found that all four techniques are reasonably fast and give sig-nificantly more compact layout than that of HTML layout engines.

Recent constraint logic programming (CLP) languages, such as HAL and Mercury, require type, mode and determinism declarations for predicates. This information allows the generation of efficient target code and the detection of many errors at compile-time. Unfortunately, mode checking in such languages is difficult. One of the main reasons is that, for each predicate mode declaration, the compiler is required to appropriately re-order literals in the predicate's definition. The task is further complicated by the need to handle complex instantiations (which interact with type declarations and higher-order predicates) and automatic initialization of solver variables. Here we define mode checking for strongly typed CLP languages which require reordering of clause body literals. In addition, we show how to handle a simple case of polymorphic modes by using the corresponding polymorphic types.

ViMer is a visual debugging environment for Mercury programs which has three main contributions. First, it employs a new execution tree representation, the layered AND-OR tree, which we believe provides a better way of visualizing backtracking in AND-OR-like trees. Second, it uses incremental constraint-solving to efficiently draw and incrementally update the visualization of the execution tree. And finally, it borrows techniques from standard tracers (such as the use of spy points to reduce the amount of tree nodes, and the placement of restrictions on the amount of information stored at each node) that help keep the tool efficient while still providing enough information for debugging.

The intelligent diagram is a recent metaphor for diagramming in which the underlying graphic editor parses the diagram as it is being constructed, performing error correction and collecting geometric constraints that capture the relationships between diagram components. During diagram manipulation a constraint solver uses these geometric constraints to maintain the diagram's semantics. We introduce the Penguins system. This automates the development of graphical editors that support the intelligent diagram metaphor. It takes a grammatical specification of a particular diagram language and generates an editor specialized for the creation, manipulation and parsing of diagrams in that visual language. We extend previous research in this area by allowing more expressive grammars, performing automatic error correction, and detailing how efficient incremental parsing has been achieved. We also provide an empirical evaluation of the system. This shows that the system can be used to generate customized editors for a wide variety of diagram languages, ranging from state transition diagrams to mathematical equations, with real-time incremental parsing and error correction.

Current constraint solving techniques for interactive graphical applications cannot satisfactorily handle constraints such as non-overlap, or containment within non-convex shapes or shapes with smooth edges. We present a generic new technique for efficiently handling such kinds of constraints based on trust regions and linear arithmetic constraint solving. Our approach is to model these more complex constraints by a dynamically changing conjunction of linear constraints. At each stage, these give a local approximation to the complex constraints. During direct manipulation, linear constraints in the current local approximation can become active indicating that the current solution is on the boundary of the trust region for the approximation. The associated complex constraint is notified and it may choose to modify the current linear approximation. Empirical evaluation demonstrates that it is possible to (re-)solve systems of linear constraints that are dynamically approximating complex constraints such as non-overlap sufficiently quickly to support direct manipulation in interactive graphical applications.

The Scalable Vector Graphics format SVG is already substantially improving graphics delivery on the web, but some important issues still remain to be addressed. In particular, SVG does not support client-side adaption of documents to different viewing conditions, such as varying screen sizes, style preferences or different device capabilities. Based on our earlier work we show how SVG can be extended with constraint-based specification of document layout to augment it with adaptive capabilities. The core of our proposal is to include one-way constraints into SVG, which offer more expressiveness than the previously suggested class of linear constraints and at the same time require substantially less computational effort.

Abstract Scalable Vector Graphics (SVG) is a language that describestwo-dimensional vector graphics for storage and distribution

Studying independence of goals has proven very useful in the context of logic programming. In particular, it has provided a formal basis for powerful automatic parallelization tools, since independence ensures that two goals may be evaluated in parallel while preserving correctness and efficiency. We extend the concept of independence to constraint logic programs (CLP) and prove that it also ensures the correctness and efficiency of the parallel evaluation of independent goals. Independence for CLP languages is more complex than for logic programming as search space preservation is necessary but no longer sufficient for ensuring correctness and efficiency. Two additional issues arise. The first is that the cost of constraint solving may depend upon the order constraints are encountered. The second is the need to handle dynamic scheduling. We clarify these issues by proposing various types of search independence and constraint solver independence, and show how they can be combined to allow different optimizations, from parallelism to intelligent backtracking. Suficient conditions for independence which can be evaluated “a priori” at run-time are also proposed. Our study also yields new insights into independence in logic programming languages. In particular, we show that search space preservation is not only a sufficient but also a necessary condition for ensuring correctness and efficiency of parallel execution.

Global analyzers traditionally read and analyze the entire program at once, in a nonincremental way. However, there are many situations which are not well suited to this simple model and which instead require reanalysis of certain parts of a program which has already been analyzed. In these cases, it appears inefficient to perform the analysis of the program again from scratch, as needs to be done with current systems. We describe how the fixed-point algorithms used in current generic analysis engines for (constraint) logic programming languages can be extended to support incremental analysis. The possible changes to a program are classified into three types: addition, deletion, and arbitrary change. For each one of these, we provide one or more algorithms for identifying the parts of the analysis that must be recomputed and for performing the actual recomputation. The potential benefits and drawbacks of these algorithms are discussed. Finally, we present some experimental results obtained with an implementation of the algorithms in the PLAI generic abstract interpretation framework. The results show significant benefits when using the proposed incremental analysis algorithms.

Cascading Style Sheets have been introduced by the W3C as a mechanism for controlling the appearance of HTML documents. In this paper, we demonstrate how constraints provide a powerful unifying formalism for declaratively understanding and specifying style sheets for web documents. With constraints we can naturally and declaratively specify complex behavior such as inheritance of properties and cascading of conflicting style rules. We give a detailed description of a constraint-based style sheet model, CCSS, which is compatible with virtually all of the CSS 2.0 specification. It allows more flexible specification of layout, and also allows the designer to provide multiple layouts that better meet the desires of the user and environmental restrictions. We also describe a prototype extension of the Amaya browser that demonstrates the feasibility of CCSS.

The intelligent diagram is a recent metaphor for diagramming in which the underlying graphic editor parses the diagram as it is being constructed, performing error correction and collecting geometric constraints which capture the relationships between diagram components.During diagram manipulation a constraint solver uses these geometric constraints to maintain the diagram's semantics.We describe the Penguins system.This automates the development of graphical editors that support the intelligent diagram metaphor.It takes a grammatical specification of a particular diagram language and generates an editor that supports the creation, manipulation and parsing of diagrams in that visual language.Our empirical results show that the system can be used to generate specialized editors for a wide variety of diagram languages, ranging from state transition diagrams to mathematical equations, with real-time incremental parsing, error correction and direct manipulation.

The incorporation of global program analysis into recent compilers for Constraint Logic Programming (CLP) languages has greatly improved the efficiency of compiled programs. We present a global analyser based on abstract interpretation. Unlike traditional optimizers, whose designs tend to be ad hoc, the analyser has been designed with flexibility in mind. The analyser is incremental, allowing substantial program transformations by a compiler without requiring redundant re-computation of analysis data. The analyser is also generic in that it can perform a large number of different program analyses. Furthermore, the analyser has an object-oriented design, enabling it to be adapted to different applications easily and allowing it to be used with various CLP languages with simple modifications. As an example of this generality, we sketch the use of the analyser in two different applications involving two distinct CLP languages: an optimizing compiler for CLP(R) programs and an application for detecting occur-check problems in Prolog programs. © 1998 John Wiley & Sons Ltd.

Constraint Logic Programming (CLP) languages extend logic programming by allowing the use of constraints from different domains such as real numbers or Boolean functions. They have proved to be ideal for expressing problems that require interactive mathematical modeling and complex combinatorial optimization problems. However, CLP languages have mainly been considered as research systems, useful for rapid prototyping, by not really competitive with more conventional programming languages where efficiency is a more important consideration. One promising approach to improving the performance of CLP systems is the use of powerful program optimizations to reduce the cost of constraint solving. We extend work in this area by describing a new optimizing compiler for the CLP language CLP(ℛ). The compiler implements six powerful optimizations: reordering of constraints, removal of redundant variables, and specialization of constraints which cannot fail. Each program optimization is designed to remove the overhead of constraint solving when possible and keep the number of constraints in the store as small as possible. We systematically evaluate the effectiveness of each optimization in isolation and in combination. Our empirical evaluation of the compiler verifies that optimizing compilation can be made efficient enough to allow compilation of real-world programs and that it is worth performing such compilation because it gives significant time and space performance improvements.

Constraints can be used to specify the desired layout of a web document, and also the behaviour of embedded applets.We present a system architecture in which both the author and the viewer can impose page layout constraints, some required and some preferential.The final appearance of the web page is thus the result of negotiation between author and viewer, where this negotiation is carried out by solving the set of required and preferential constraints imposed by both parties.We identify two plausible system architectures, based on different ways of dividing the work of constraint solving between web server and web client.Finally, we describe an implementation of a prototype constraintbased web authoring system and viewer, which also provides constraint-based embedded applets.

Linear equality and inequality constraints arise naturally in specifying many aspects of user interfaces, such as requiring that one window be to the left of another, requiring that a pane occupy the leftmost l/3 of a window, or preferring that an object be contained within a rectangle if possible.Current constraint solvers designed for UI applications cannot efficiently handle simultaneous linear equations and inequalities.This is a major limitation.We describe incremental algorithms based on the dual simplex and active set methods that can solve such systems of constraints efficiently.

Traditional logic programming languages, such as Prolog, use a fixed left-to-right atom scheduling rule. Recent logic programming languages, however, usually provide more flexible scheduling in which computation generally proceed left-to-right but in which some calls are dynamically “delayed” until their arguments are sufficiently instantiated to allow the call to run efficiently. Such dynamic scheduling has a significant cost. We give a framework for the global analysis of logic programming languages with dynamic scheduling and show that program analysis based on this framework supports optimizations which remove much of the overhead of dynamic scheduling.

Concurrent logic languages specify reactive systems which consist of collections of communicating processes. The presence of unintended suspended computations is a common programming error which is difficult to detect using standard debugging and testing techniques. We develop a number of analyses, based on abstract interpretation, which succeed if a program is definitely suspension free. If an analysis fails, the program may, or may not, be suspension free. Examples demonstrate that the analyses are practically useful. They are conceptually simple and easy to justify because they are based directly on the transition system semantics of concurrent logic programs. A naive analysis must consider all scheduling policies . However, it is proven that for our analyses it suffices to consider only one scheduling policy, allowing for efficient implementation.

Logic-programming languages are based on a principle of separation “logic” and “control.”. This means that they can be given simple model-theoretic semantics without regard to any particular execution mechanism (or proof procedure, viewing execution as theorem proving). Although the separation is desirable from a semantical point of view, it makes sound, efficient implementation of logic-programming languages difficult. The lack of “control information” in programs calls for complex data-flow analysis techniques to guide execution. Since data-flow analysis furthermore finds extensive use in error-finding and transformation tools, there is a need for a simple and powerful theory of data-flow analysis of logic programs. This paper offers such a theory, based on F. Nielson's extension of P. Cousot and R. Cousot's abstract interpretation . We present a denotational definition of the semantics of definite logic programs. This definition is of interest in its own right because of its compactness. Stepwise we develop the definition into a generic data-flow analysis that encompasses a large class of data-flow analyses based on the SLD execution model. We exemplify one instance of the definition by developing a provably correct groundness analysis to predict how variables may be bound to ground terms during execution. We also discuss implementation issues and related work.

A framework for the analysis of concurrent constraint programming (CCP) is proposed. The approach is based on simple denotational semantics that approximate the usual semantics in the sense that they give a superset of the input-output relation of a CCP program. Analyses based on these semantics can be easily and efficiently implemented using standard techniques from the analysis of logic programs.>

Central to constraint logic programming (CLP) languages is the notion of a global constraint solver which is queried to direct execution and to which constraints are monotonically added. We present a methodology for use in the compilation of CLP languages which is designed to reduce the overhead of the global constraint solver. This methododology is based on three optimizations. The first, refinement, involves adding new constraints, which in effect make information available earlier in the computation, guiding subsequent execution away from unprofitable choices. The second, removal, involves eliminating constraints from the solver when they are redundant. The last, reordering, involves moving constraint addition later and constraint removal earlier in the computation. Determining the applicability of each optimization requires sophisticated global analysis. These analyses are based on abstract interpretation and provide information about potential and definite interaction between constraints.

We present a method for converting a system of multivariate Boolean constraints into a sequence of univariate range queries of the type supported by current spatial databases. The method relies on the transformation of a Boolean constraint system into triangular form. We extend previous results in this area by considering negative as well as positive constraints. We also present a method to approximate triangular Boolean constraints by bounding box constraints. 1 Introduction In spatial database systems, there is a gap between the high-level query language required by applications and users, and the simpler query language supported by the underlying spatial data-structure. Typically, applications such as geographic information systems [5, 8, 10], visual language parsers [7], VLSI design rule checkers [14], require a query language in which queries and integrity constraints may be expressed over a number of variables subject to Boolean constraints (that is, constraints over sets). In ...